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

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

1846C - Рудольф и очередное соревнование

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?

SevenRedSuns

2 months 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

2 months 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