Advertisement
Kevin_Zhang

Untitled

Dec 16th, 2020
754
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.81 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define pb emplace_back
  3. #define AI(i) begin(i), end(i)
  4. using namespace std;
  5. using ll = long long;
  6. template<class T>
  7. bool chmax(T &val, T nv) { return val < nv ? (val = nv, true) : false; }
  8. template<class T>
  9. bool chmin(T &val, T nv) { return nv < val ? (val = nv, true) : false; }
  10. #ifdef KEV
  11. #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
  12. void kout() {cerr << endl;}
  13. template<class T1, class ...T2>
  14. void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); }
  15. template<class T>
  16. void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
  17. #else
  18. #define DE(...) 0
  19. #define debug(...) 0
  20. #endif
  21. // What I should check
  22. // 1. overflow
  23. // 2. corner cases
  24. // Enjoy the problem instead of hurrying to AC
  25. // Good luck !
  26. /*
  27. ID: ckevin31
  28. LANG: C++14
  29. TASK:
  30. */
  31. #ifndef KEV
  32. inline void IO(string name) {
  33.     freopen((name + ".in").c_str(), "r", stdin);
  34.     freopen((name + ".out").c_str(), "w", stdout);
  35. }
  36. #else
  37. inline void IO(string name){}
  38. #endif
  39. int32_t main() {
  40.     ios_base::sync_with_stdio(0), cin.tie(0);
  41.     IO("gangs");
  42.     int n, m;
  43.     cin >> n >> m;
  44.     vector<int> cnt(m), res;
  45.     for (int &i : cnt) cin >> i;
  46.  
  47.     int mx = m == 1 ? 0 : *max_element(cnt.begin()+1, cnt.end());
  48.  
  49.     // x is answer, y is other 1s that we need to put in the front of the answer
  50.     int x = min(cnt[0], n - mx * 2), y = cnt[0] - x;
  51.     // if number of numbers other than one is odd, then we need to eliminate at least one with them
  52.     if ((n - cnt[0]) % 2 == 1 && y == 0) ++y, --x;
  53.  
  54.     assert(x + y == cnt[0] && min(x, y) >= 0);
  55.  
  56.     if (x <= 0) return cout << "NO\n", 0;
  57.  
  58.     // Fid : The id of element in stack, Fcnt : The number of element in stack
  59.    
  60.     int Fid = 0, Fcnt = 0, sum = n - x;
  61.  
  62.     // We need the info of cur_max_element,
  63.     // the number of elements left other than a bunch of ones
  64.     vector<int> cntcnt(n + 1);
  65.     for (int i = 1;i < m;++i) ++cntcnt[ cnt[i] ];
  66.     int mxpointer = 1, cur_mx_cnt = n;
  67.  
  68.     auto put = [&](int id) {
  69.         //cerr << "Put " << id+1 << endl;
  70.         if (id == Fid || Fcnt == 0)
  71.             ++Fcnt, Fid = id;
  72.         else
  73.             --Fcnt;
  74.         if (id) {
  75.             --cntcnt[ cnt[id]-- ], --sum;
  76.             if (cnt[id] >= 0)
  77.                 ++cntcnt[ cnt[id] ];
  78.         }
  79.         res.pb(id);
  80.     };
  81.  
  82.     auto get_most_freq = [&]() {
  83.         while (cur_mx_cnt && cntcnt[ cur_mx_cnt ] == 0) --cur_mx_cnt;
  84.         while (mxpointer < m && cnt[mxpointer] < cur_mx_cnt) ++mxpointer;
  85.         return min(mxpointer, m - 1);
  86.     };
  87.     auto valid = [&](int put_id) {
  88.         int g = get_most_freq();
  89.         if (put_id == g || Fcnt == 0 || Fid != put_id) return true;
  90.         return cnt[g] * 2 <= sum + Fcnt - 2;
  91.     };
  92.  
  93.     for (int i = 0;i < y;++i) put(0);
  94.  
  95.     for (int i = 1;i < m;++i) {
  96.         while (cnt[i]) {
  97.             if (valid(i))
  98.                 put(i);
  99.             else
  100.                 put(get_most_freq());
  101.         }
  102.     }
  103.  
  104.     for (int i = 0;i < x;++i) put(0);
  105.  
  106.     cout << "YES\n" << x << '\n';
  107.     for (int u : res)
  108.         cout << u+1 << '\n';
  109. }
  110.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement