Advertisement
Josif_tepe

Untitled

Mar 27th, 2021
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     ios_base::sync_with_stdio(false);
  8.     int n;
  9.     cin >> n;
  10.     int k;
  11.     cin >> k;
  12.     int a[n];
  13.     int pref_sum[n];
  14.     int sum = 0;
  15.     for(int i = 0; i < n; i++) {
  16.         cin >> a[i];
  17.         if(a[i] == 0) {
  18.             sum += 1;
  19.         }
  20.         pref_sum[i] = sum;
  21.     }
  22.     int max_fixed = 0;
  23.     for(int i = 0; i < n; i++) {
  24.         int L = i + 1;
  25.         int R = n - 1;
  26.        
  27.         while(L <= R) {
  28.             int middle = (L + R) / 2;
  29.             int zeros = pref_sum[middle];
  30.             if(i - 1 >= 0) {
  31.                 zeros -= pref_sum[i - 1];
  32.             }
  33.             if(zeros <= k) {
  34.                 max_fixed = max(max_fixed, middle - i + 1);
  35.                 L = middle + 1;
  36.             }
  37.             else {
  38.                 R = middle - 1;
  39.             }
  40.         }
  41.     }
  42.    
  43.     for(int i = 0; i < n; i++) {
  44.         int L = i + 1;
  45.         int R = n - 1;
  46.        
  47.         while(L <= R) {
  48.             int middle = (L + R) / 2;
  49.             int zeros = pref_sum[middle];
  50.             if(i - 1 >= 0) {
  51.                 zeros -= pref_sum[i - 1];
  52.             }
  53.             if(zeros <= k) {
  54.                 if(max_fixed == middle - i + 1) {
  55.                     cout << max_fixed << endl;
  56.                     for(int j = i; j <= middle; j++) {
  57.                         if(a[j] == 0) {
  58.                             cout << j + 1 << " ";
  59.                         }
  60.                     }
  61.                     return 0;
  62.                 }
  63.                 L = middle + 1;
  64.             }
  65.             else {
  66.                 R = middle - 1;
  67.             }
  68.         }
  69.     }
  70.    
  71.    
  72.     return 0;
  73. }
  74.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement