fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int getPossibleCount(vector<int> totalEfficiency) {
  5. 	int n = totalEfficiency.size();
  6.     vector<int> U;
  7.     U.reserve(n);
  8.  
  9.     int current_emp = 1;
  10.     for (int te : totalEfficiency) {
  11.         while (current_emp < te) {
  12.             U.push_back(current_emp);
  13.             current_emp++;
  14.         }
  15.         current_emp++;
  16.     }
  17.     // Add any remaining employees up to 2n
  18.     while (current_emp <= 2 * n) {
  19.         U.push_back(current_emp);
  20.         current_emp++;
  21.     }
  22.  
  23.     int low = 0, high = n;
  24.     int maxX = -1; 
  25.  
  26.     while (low <= high) {
  27.         int mid = low + (high - low) / 2;
  28.         bool ok = true;
  29.  
  30.         for (int i = 0; i < mid; ++i) {
  31.             if (totalEfficiency[i] >= U[n - mid + i]) {
  32.                 ok = false;
  33.                 break;
  34.             }
  35.         }
  36.  
  37.         if (ok) {
  38.             maxX = mid;
  39.             low = mid + 1; // Try larger x
  40.         } else {
  41.             high = mid - 1;
  42.         }
  43.     }
  44.  
  45.     low = 0; high = n;
  46.     int minX = n + 1; 
  47.  
  48.     while (low <= high) {
  49.         int mid = low + (high - low) / 2;
  50.         bool ok = true;
  51.  
  52.         // Check: U[0...n-mid-1] < T[mid...n-1] element-wise
  53.         int count = n - mid;
  54.         for (int i = 0; i < count; ++i) {
  55.             if (U[i] >= totalEfficiency[mid + i]) {
  56.                 ok = false;
  57.                 break;
  58.             }
  59.         }
  60.  
  61.         if (ok) {
  62.             minX = mid;
  63.             high = mid - 1; // Try smaller x
  64.         } else {
  65.             low = mid + 1;
  66.         }
  67.     }
  68.  
  69.     // 4. Calculate intersection size
  70.     if (maxX < minX) return 0;
  71.  
  72.     return maxX - minX + 1;
  73. }
  74.  
  75. int main() {
  76. 	int n;
  77. 	cin >> n;
  78. 	vector<int> v(n);
  79. 	for (int i=0;i<n;i++) cin >> v[i];
  80.  
  81. 	cout << getPossibleCount(v) << endl;
  82. }
  83.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
3
1 2 4
stdout
copy 
2
https://ideone.com/mkmpY7
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!