Advertisement
Korotkodul

N4 3

Nov 4th, 2022
698
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int, int>
  11. #define pb(x) push_back(x)
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v) {
  17.     for (auto x : v) cout << x << ' ';
  18.     cout << "\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v) {
  22.     for (auto x : v) cout << x << ' ';
  23.     cout << "\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v) {
  28.     for (auto x : v) cv(x);
  29.     cout << "\n";
  30. }
  31.  
  32. void cvb(vector <bool> v) {
  33.     for (bool x : v) cout << x << ' ';
  34.     cout << "\n";
  35. }
  36.  
  37. void cvs(vector <string>  v) {
  38.     for (auto a : v) {
  39.         cout << a << "\n";
  40.     }
  41. }
  42.  
  43. void cvp(vector <pii> a) {
  44.     for (auto p : a) {
  45.         cout << p.first << ' ' << p.second << "\n";
  46.     }
  47.     cout << "\n";
  48. }
  49. #include <ctime>
  50.  
  51. bool sh = 1;
  52. int N, n;
  53.  
  54. vector <int> gen() {
  55.     srand(time(0));
  56.     n = rand() % 5 + 2;
  57.     vector <int> a;
  58.     for (int i = 0; i < n; ++i) {
  59.         int x = rand() % 10 + 1;
  60.         a.pb(x);
  61.         N += x;
  62.     }
  63.     sort(a.begin(), a.end());
  64.     reverse(a.begin(), a.end());
  65.     //cv(a);
  66.     return a;
  67. }
  68.  
  69. bool ok(vector <int> a) {
  70.     for (int i = 0; i < a.size() - 1; ++i) {
  71.         if (a[i] == a[i + 1]) {
  72.             return 0;
  73.         }
  74.     }
  75.     return 1;
  76. }
  77.  
  78. vector <int> my(vector <int> a) {
  79.     int dif = a[0] - a[1] - 1;
  80.     a[0] -= dif;
  81.     vector <int> ans(N);
  82.     int id = -1, cnt = 0;
  83.     int to = n;
  84.     if (sh) {
  85.         cout << "A\n";
  86.     }
  87.     int nxt = n;
  88.     while (cnt < N) {
  89.         to = nxt;
  90.         int j = -1;
  91.         if (sh) {
  92.             cout << "B\n";
  93.             cout << "to = " << to << "\n";
  94.             cout << "cnt = " << cnt << "\n";
  95.         }
  96.         while (j + 1 < to) {
  97.             id++;
  98.             if (sh) cout << "id j = " << id << ' ' << j << "\n";
  99.             if (sh) {
  100.                 cout << "a\n";
  101.                 cv(a);
  102.                 cout << "dif = " << dif << "\n";
  103.             }
  104.             if (j == -1 && dif > 0) {
  105.                 if (sh) {
  106.                     cout << "C\n";
  107.                 }
  108.                 ans[id] = 0;
  109.                 j = 0;
  110.                 a[0]--;
  111.                 cnt++;
  112.                 continue;
  113.             }
  114.             if (dif > 0) {
  115.                 if (sh) {
  116.                     //cout << "del dif\n";
  117.                     cout << "D\n";
  118.                 }
  119.                 if (id == 0 || id > 0 && ans[id - 1] != 0) {
  120.                     ans[id] = 0;
  121.                     dif--;
  122.                     cnt++;
  123.                     continue;
  124.                 }
  125.             }
  126.  
  127.             j++;
  128.             a[j]--;
  129.             cnt++;
  130.             if (sh) {
  131.                 cout << "E\n";
  132.                 cout << "j = " << j << "\n";
  133.             }
  134.             if (sh) {
  135.                 //cout << "just go\n";
  136.             }
  137.             ans[id] = j;
  138.             if (a[j] == 0) {
  139.                 nxt = min(nxt, j);
  140.             }
  141.         }
  142.     }
  143.     if (ok(ans)) {
  144.         return ans;
  145.     }
  146.     return {-1};
  147. }
  148.  
  149. bool random = 1;
  150.  
  151. int main() {
  152.     /*ios::sync_with_stdio(0);
  153.     cin.tie(0);
  154.     cout.tie(0);*/
  155.  
  156.     vector <int> a;
  157.     if (sh && random) {
  158.         a = gen();
  159.     } else if (sh) {
  160.         cin >> n;
  161.         a.resize(n);
  162.         for (int &i: a) {
  163.                 cin >> i;
  164.                 N += i;
  165.         }
  166.         sort(a.begin(), a.end());
  167.         reverse(a.begin(), a.end());
  168.     }
  169.  
  170.     if (sh) {
  171.         cout << "N = " << N <<"\n";
  172.         cout << "a\n";
  173.         cv(a);
  174.     }
  175.  
  176.     vector <int> r = my(a);
  177.     if (sh) {
  178.         cout << "r\n";
  179.         cv(r);
  180.     }
  181. }
  182. /*
  183. N = 58
  184. a
  185.  
  186. 5
  187. 18 17 11 8 4
  188. */
  189.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement