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	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

#	User	Contrib.
1	maomao90	164
2	Um_nik	163
3	atcoder_official	158
3	cry	158
3	-is-this-fft-	158
6	awoo	156
7	adamant	154
7	nor	154
9	TheScrasse	153
10	Dominater069	152

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 (1)

Write comment?

Jsanchez1011

56 minutes 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's blog