fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Problem: Each person i has constraints on team composition
  5. // lo[i] = max number of people with LOWER skill than i in the team
  6. // hi[i] = max number of people with HIGHER skill than i in the team
  7. // Find maximum team size where everyone's constraints are satisfied
  8. // IMPORTANT: Selected people occupy positions by skill order
  9.  
  10. // Check if we can make a valid team of size sz
  11. bool check(int sz, vector<int>& lo, vector<int>& hi) {
  12.     int n = lo.size() - 1;
  13.  
  14.     // For person i at position pos in a team of size sz:
  15.     // - (pos-1) people have lower skill (better positions)
  16.     // - (sz-pos) people have higher skill (worse positions)
  17.     // Valid if: pos-1 <= lo[i] AND sz-pos <= hi[i]
  18.     // Rearranging: max(1, sz-hi[i]) <= pos <= min(sz, lo[i]+1)
  19.  
  20.     // Precompute valid position ranges for each person
  21.     vector<pair<int, int>> ranges(n + 1);
  22.     for (int i = 1; i <= n; i++) {
  23.         int L = max(1, sz - hi[i]);
  24.         int R = min(sz, lo[i] + 1);
  25.         ranges[i] = {L, R};
  26.     }
  27.  
  28.     // Greedy: fill positions 1, 2, ..., sz
  29.     // For each position, pick the smallest skill index that can go there
  30.     int nextPos = 1;
  31.  
  32.     for (int skill = 1; skill <= n && nextPos <= sz; skill++) {
  33.         int L = ranges[skill].first;
  34.         int R = ranges[skill].second;
  35.  
  36.         // Can person with this skill be placed at nextPos?
  37.         if (L <= nextPos && nextPos <= R) {
  38.             nextPos++;  // Assign this person to nextPos, move to next position
  39.         }
  40.         // Otherwise skip this person (can't use them)
  41.     }
  42.  
  43.     // Successfully filled all sz positions?
  44.     return nextPos > sz;
  45. }
  46.  
  47. int main() {
  48.     ios::sync_with_stdio(false);
  49.     cin.tie(nullptr);
  50.  
  51.     int n;
  52.     cin >> n;
  53.  
  54.     // lo[i] = max number of people with lower skill (in selected team)
  55.     // hi[i] = max number of people with higher skill (in selected team)
  56.     vector<int> lo(n + 1), hi(n + 1);
  57.  
  58.     for (int i = 1; i <= n; i++) cin >> lo[i];
  59.     for (int i = 1; i <= n; i++) cin >> hi[i];
  60.  
  61.     // Binary search on maximum team size
  62.     int l = 0, r = n;
  63.  
  64.     while (l < r) {
  65.         int m = (l + r + 1) / 2;
  66.  
  67.         if (check(m, lo, hi)) {
  68.             l = m;  // Can make team of size m, try bigger
  69.         } else {
  70.             r = m - 1;  // Cannot make team of size m, try smaller
  71.         }
  72.     }
  73.  
  74.     cout << l << "\n";
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/7LK5jz
language:
C++14 (gcc 8.3)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!