Advertisement
erek1e

IOI '13 P5 - Robots (Standard I/O)

Jun 18th, 2022
999
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     int A, B, T;
  10.     cin >> A >> B >> T;
  11.     vector<int> X(A), Y(B);
  12.     for (int &x : X) cin >> x;
  13.     for (int &y : Y) cin >> y;
  14.     vector<int> W(T), S(T);
  15.     for (int i = 0; i < T; ++i) cin >> W[i] >> S[i];
  16.  
  17.     sort(X.begin(), X.end());
  18.     sort(Y.begin(), Y.end());
  19.  
  20.     vector<pair<int, int>> byW(T);
  21.     for (int i = 0; i < T; ++i) byW[i] = {W[i], i};
  22.     sort(byW.begin(), byW.end());
  23.  
  24.     priority_queue<pair<int, int>> byS;
  25.    
  26.     int left = 0, right = T+1;
  27.     while (left+1 < right) {
  28.         int k = (left + right) / 2; // is it possible in at most k minutes
  29.  
  30.         // Get all "weak" robots to take toys as large as possible
  31.         int nextToy = 0;
  32.         for (int i = 0; i < A; ++i) {
  33.             while (nextToy < T && byW[nextToy].first < X[i]) {
  34.                 byS.emplace(S[byW[nextToy].second], byW[nextToy].second);
  35.                 nextToy++;
  36.             }
  37.             for (int j = 0; j < k && !byS.empty(); ++j) byS.pop(); // take k largest
  38.         }
  39.         while (nextToy < T) {
  40.             byS.emplace(S[byW[nextToy].second], byW[nextToy].second);
  41.             nextToy++;
  42.         }
  43.  
  44.         // Get all the "small" robots to take the rest
  45.         for (int i = B-1; i >= 0 && !byS.empty(); --i) {
  46.             if (byS.top().first >= Y[i]) continue;
  47.             for (int j = 0; !byS.empty() && j < k; ++j) byS.pop();
  48.         }
  49.        
  50.         if (byS.empty()) right = k;
  51.         else left = k;
  52.  
  53.         while (!byS.empty()) byS.pop();
  54.     }
  55.     cout << (right > T ? -1 : right) << endl;
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement