Samkit5025

Untitled

Sep 21st, 2022
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. bool check(vector<vector<int>> &a, int k)
  6. {
  7.     int rich = k - 1;
  8.     int poor = 0;
  9.     int count = 0;
  10.     for (int i = 0; i < a.size(); i++)
  11.     {
  12.         if (a[i][0] >= rich && a[i][1] >= poor)
  13.         {
  14.             rich--;
  15.             poor++;
  16.             count++;
  17.         }
  18.     }
  19.     return count >= k;
  20. }
  21.  
  22. int maximumQuestions(int N, vector<vector<int>> &A)
  23. {
  24.  
  25.     int start = 1;
  26.     int end = N;
  27.     int ans = 0;
  28.     while (start <= end)
  29.     {
  30.         int mid = start + (end - start) / 2;
  31.         if (check(A, mid))
  32.         {
  33.             ans = mid;
  34.             start = mid + 1;
  35.         }
  36.         else
  37.         {
  38.             end = mid - 1;
  39.         }
  40.     }
  41.  
  42.     return ans;
  43. }
  44.  
  45. signed main()
  46. {
  47.     int N;
  48.     cin >> N;
  49.  
  50.     vector<vector<int>> A(N, vector<int>(2));
  51.     for (int i = 0; i < N; i++)
  52.     {
  53.         cin >> A[i][0] >> A[i][1];
  54.     }
  55.  
  56.     cout << maximumQuestions(N, A) << endl;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment