Advertisement
Josif_tepe

Untitled

Apr 7th, 2022
652
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. int main() {
  8.     ios_base::sync_with_stdio(false);
  9.     int len, buses;
  10.     cin >> len >> buses;
  11.     vector<int> v(buses);
  12.     vector<int> occupied(len + 1, 0);
  13.     for(int& x : v) {
  14.         cin >> x;
  15.         occupied[x] = -1;
  16.     }
  17.     int bus_length, cnt;
  18.     cin >> cnt >> bus_length;
  19.     int tmp = 0;
  20.     vector<pair<int, int> > spaces;
  21.     int sum = 0;
  22.     int idx = -1;
  23.     for(int i = 1; i <= len; i++) {
  24.         if(occupied[i] == -1 and tmp > 0) {
  25.             spaces.push_back(make_pair(tmp / bus_length, idx));
  26.             idx = -1;
  27.             sum += (tmp / bus_length);
  28.             tmp = 0;
  29.         }
  30.         else if(occupied[i] == 0){
  31.             if(idx == -1) {
  32.                 idx = i;
  33.             }
  34.             ++tmp;
  35.         }
  36.     }
  37.     if(tmp > 0) {
  38.         spaces.push_back(make_pair(tmp / bus_length, idx));
  39.         sum += (tmp / bus_length);
  40.     }
  41.     sort(spaces.rbegin(), spaces.rend());
  42.     int ret = 0;
  43.     vector<pair<int, int> > ans;
  44.     for(int i = 0; i < (int) spaces.size(); i++) {
  45.         if(sum - spaces[i].first >= cnt) {
  46.             sum -= spaces[i].first;
  47.             ret += spaces[i].first;
  48.             ans.push_back(make_pair(spaces[i].first, spaces[i].second));
  49.         }
  50.         else {
  51.             ret += sum + 1 - cnt;
  52.             ans.push_back(make_pair((sum + 1 - cnt), spaces[i].second));
  53.             sum -= (sum + 1 - cnt);
  54.             break;
  55.         }
  56.     }
  57.     cout << ret << endl;
  58.     for(int i = 0; i < (int) ans.size(); i++) {
  59. //        cout << ans[i].first << " " << ans[i].second << endl;
  60.         for(int j = ans[i].second + bus_length - 1, broken = 0; broken < ans[i].first; j += bus_length, broken++) {
  61.             cout << j << " " ;
  62.         }
  63.     }
  64.     return 0;
  65. }
Advertisement
RAW Paste Data Copied
Advertisement