fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int getPossibleCount(vector<int>& A) {
  6.     int n = A.size();
  7.     vector<char> present(2*n + 1, 0);
  8.     for (int v : A) present[v] = 1;
  9.     vector<int> B; B.reserve(n);
  10.     for (int i = 1; i <= 2*n; ++i) if (!present[i]) B.push_back(i);
  11.  
  12.     // compute maxWins: greedily match each a to smallest b > a
  13.     int maxWins = 0;
  14.     int j = 0;
  15.     for (int i = 0; i < n && j < n; ++i) {
  16.         while (j < n && B[j] <= A[i]) ++j;
  17.         if (j == n) break;
  18.         ++maxWins;
  19.         ++j;
  20.     }
  21.  
  22.     // compute maxLosses: greedily match to maximize a > b
  23.     int maxLosses = 0;
  24.     int leftB = 0, rightB = n - 1;
  25.     for (int i = 0; i < n; ++i) {
  26.         if (leftB <= rightB && B[leftB] < A[i]) {
  27.             // use smallest b that is < a to produce a > b (a is max)
  28.             ++maxLosses;
  29.             ++leftB;
  30.         } else {
  31.             // cannot produce a > b; consume largest remaining b
  32.             --rightB;
  33.         }
  34.     }
  35.     int minWins = n - maxLosses;
  36.  
  37.     int ans = max(0, maxWins - minWins + 1);
  38.     return ans;
  39. }
  40.  
  41. int main() {
  42. 	int n;
  43. 	cin >> n;
  44. 	vector<int> v(n);
  45. 	for (int i=0;i<n;i++) cin >> v[i];
  46.  
  47. 	cout << getPossibleCount(v) << endl;
  48. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
2
3 4
stdout 
1
https://ideone.com/6dyxsV
language:
C++14 (gcc 8.3)
created:
2 days 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!