Advertisement
Josif_tepe

Untitled

Apr 13th, 2025
314
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5.  
  6.  
  7. int main() {
  8.     ios_base::sync_with_stdio(false);
  9.     int len, buses;
  10.     cin >> len >> buses;
  11.    
  12.     vector<int> v(buses);
  13.     vector<bool> occupied(len + 1, false);
  14.    
  15.     for(int i = 0; i < buses; i++) {
  16.         cin >> v[i];
  17.         occupied[v[i]] = true;
  18.     }
  19.    
  20.     int bus_length, cnt;
  21.     cin >> cnt >> bus_length;
  22.    
  23.     vector<pair<int, int>> spaces;
  24.    
  25.     int tmp = 0;
  26.     int idx = -1;
  27.     int sum = 0;
  28.     for(int i = 1; i <= len; i++) {
  29.         if(occupied[i] and tmp > 0) {
  30.             spaces.push_back({tmp / bus_length, idx});
  31.             idx = -1;
  32.             sum += tmp / bus_length;
  33.             tmp = 0;
  34.         }
  35.         else if(!occupied[i]) {
  36.             if(idx == -1) {
  37.                 idx = i;
  38.             }
  39.             tmp++;
  40.         }
  41.     }
  42.     if(tmp > 0) {
  43.         spaces.push_back({tmp / bus_length, idx});
  44.         sum += tmp / bus_length;
  45.        
  46.  
  47.     }
  48.     sort(spaces.rbegin(), spaces.rend());
  49.     int res = 0;
  50.     vector<pair<int, int>> ans;
  51.     for(int i = 0; i < (int) spaces.size(); i++) {
  52.         if(sum - spaces[i].first >= cnt) {
  53.             sum -= spaces[i].first;
  54.             res += spaces[i].first;
  55.             ans.push_back(spaces[i]);
  56.         }
  57.         else {
  58.             res += sum + 1 - cnt;
  59.             ans.push_back({sum + 1 - cnt, spaces[i].second});
  60.             sum -= (sum + 1 - cnt);
  61.             break;
  62.         }
  63.     }
  64.    
  65.     cout << res << endl;
  66.     for(int i = 0; i < (int) ans.size(); i++) {
  67.         for(int j = ans[i].second + bus_length - 1, broke = 0; broke < ans[i].first; broke++, j += bus_length) {
  68.             cout << j << " ";
  69.         }
  70.     }
  71.     return 0;
  72. }
  73.  
  74.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement