3rd time writing this blog since no one could find the error of a 1200-rated problem before!

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

1846C - Rudolf and the Another Competition

My Code

using ll = long long;

void solve() {
   int n, m, t;
   cin >> n >> m >> t;
   vector<vector<int>> a(n, vector<int>(m));
   vector<tuple<int, ll, int>> tp; 
   for (int i = 0; i < n; i++) {
      for (int k = 0; k < m; k++) {
         cin >> a[i][k];
      }
      sort(a[i].begin(), a[i].end());
      int cnt = 0;
      int sum = 0;
      ll pen = 0;
      for (int k = 0; k < m; k++) {
         if (sum + a[i][k] <= t) {
            sum += a[i][k];
            pen += sum; 
            cnt += 1;
         } else {
            break;
         }
      }
      tp.emplace_back(cnt, pen, i);
   }
   sort(tp.begin(), tp.end(), [&](tuple<int, ll, int> a, tuple<int, ll, int> b) {
      if (get<0>(a) == get<0>(b)) {
         return get<1>(a) < get<1>(b);
      } 
      return get<0>(a) > get<0>(b);
   });
   int ans = 0;
   for (int i = 0; i < n; i++) {
      if (get<2>(tp[i]) == 0) {
         ans = i + 1;
         break;
      }
   }
   cout << ans << "\n";
}

I don't know why my code is not working even though the approach is correct, and I don't see anything wrong with my code. Even the 10th test case where it failed should give the right answer, according to me. I would be grateful if you could find out where the error is.

Comments (4)

Write comment?

Jsanchez1011

6 weeks ago, # |

yeah i found your problem.

The problem is how you find the rudolf result, you put rudolf the id 0, but in the sort function you not drive the case where the amount of problems and the penalizing are the same.

For example imagine there is two competidor, they have 1 1 0, and 1 1 1, so at the moment to sort there are two possibles case: {[1 1 0], [1 1 1]} or {[1 1 1], [1 1 0]}. And in the stament say you have to get the first if there is and draw.

The solution

You can compare by problems and pen for found the score of rudolf, or put another case (the id) in the lambda sort when the problems and the penalize are equal

if (get<0>(a) == get<0>(b) && get<1>(a) == get<1>(b)){
         return get<2>(a) < get<2> (b);
}

→ Reply

Adityaxv

6 weeks ago, # ^ |

Thanks for replying! Your solution worked.

If we sort vector<pair<int, int>> pr using the default std::sort function, it automatically sorts the pr.second value in non-decreasing order if the pr.first values are equal.

So, I always thought that we don't need to specify the sort function if we want their value sorted in non-decreasing order if the previous values are equal.

But guess it is not true for more than two values! I even implemented your approach before, but I made mistakes in implementing that :(

i'm not sure, but when you used a personalized comp, you replace the default like you said, so if you will use a lambda sort, remember that you are doing is replace the default comparator to your new fuction, so be sure in thinking in all cases...

(please correct me if i'm wrong)

I checked with vector<pair<int, int>>. You are right! We have modified the sort function so it won't sort automatically the non-specified value in a non-decreasing order.

Adityaxv's blog