Advertisement
El_GEMMY

D

Jul 24th, 2022
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.20 KB | None | 0 0
  1. // Those who cannot remember the past are
  2. // condemned to repeat it (use DP -_-)
  3. // - George Santayana
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11.  
  12. #define all(v) v.begin(), v.end()
  13. #define rall(v) v.rbegin(), v.rend()
  14. #define ll long long
  15. #define ull unsigned long long
  16. #define MOD 1000000007
  17. #define PI acos(-1)
  18. //#define ceil(a, b) (((a) / (b)) + ((a) % (b) ? 1 : 0))
  19. #define imin INT_MIN
  20. #define imax INT_MAX
  21. #define llmax LLONG_MAX
  22. #define llmin LLONG_MIN
  23. #define inf 2000000000
  24. #define nl '\n'
  25. #define ppcnt __builtin_popcount
  26. #define ppcntll __builtin_popcountll
  27. #define clz __builtin_clz
  28. #define clzll __builtin_clzll
  29. #define ctz __builtin_ctz
  30. #define ctzll __builtin_ctzll
  31. #define modulo(a, b, mod) ((((a) % (mod)) + ((b) % (mod))) % (mod))
  32. #define cnte(v, x) count(all(v), (x))
  33. #define mine(v) min_element(all(v))
  34. #define maxe(v) max_element(all(v))
  35. #define updmin(a, b) a = min(a, b)
  36. #define updmax(a, b) a = max(a, b)
  37. #define findmod(x, m) x = ((x) % (m) + (m)) % m
  38. #define getmod(x, m) ((x) % (m) + (m)) % (m)
  39. #define debug(x) cout << "x: " << (x) << nl;
  40. #define debug2(x, y) cout << "x: " << (x) << " y: " << y << nl;
  41. #define ordered_set tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
  42. #define ordered_map tree<int, int, less<>, rb_tree_tag, tree_order_statistics_node_update>
  43.  
  44. //vector<int> dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};
  45. vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
  46.  
  47. template<typename T = int> istream& operator>>(istream& in, vector<pair<int, int>>& v){
  48.     for (auto& [x, y] : v) in >> x >> y;
  49.     return in;
  50. }
  51.  
  52. template<typename T = int> istream& operator>>(istream& in, vector<T>& v){
  53.     for (T& i : v) in >> i;
  54.     return in;
  55. }
  56.  
  57. template<typename T = int> ostream& operator<<(ostream& out, const vector<T>& v){
  58.     for (const T& x : v)
  59.         out << x << ' ';
  60.     return out;
  61. }
  62.  
  63. template<typename T = pair<int, int>> ostream& operator << (ostream& out, const vector<pair<int, int>>& v){
  64.     for(auto& [x, y] : v){
  65.         out << x << ' ' << y << nl;
  66.     }
  67.     return out;
  68. }
  69.  
  70. void Start_Crushing() {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(nullptr);
  73.     cout.tie(nullptr);
  74. #ifndef ONLINE_JUDGE
  75.     freopen("input.txt", "r", stdin);
  76.     freopen("output.txt", "w", stdout);
  77. #endif
  78. }
  79.  
  80. void solve() {
  81.     int n; cin >> n;
  82.     vector<int> v(n); cin >> v;
  83.  
  84.     priority_queue<int> pq;
  85.  
  86.     // 1 2 3 4
  87.     // 2 2 2 2
  88.     // 2 3 4 5
  89.  
  90.     // map<freq, set<courses>> -> mp[freq].begin(), mp[freq].erase(begin), mp[freq - 1].insert(begin)
  91.  
  92.     // pq -> 4 4 3 2
  93.  
  94.     map<int, set<int>> lectures;
  95.  
  96.     int idx = 1;
  97.     for(auto& i : v){
  98.         pq.push(i);
  99.         lectures[i].insert(idx++);
  100.     }
  101.  
  102.     bool ok = true;
  103.  
  104.     vector<int> ans;
  105.     while(not pq.empty()){
  106.         int curr_freq = pq.top();
  107.         pq.pop();
  108.  
  109.         if(lectures[curr_freq].empty()){
  110.             ok = false;
  111.             break;
  112.         }
  113.  
  114.         auto it = lectures[curr_freq].begin();
  115.         while(not ans.empty() and it != lectures[curr_freq].end() and *it == ans.back())
  116.             it++;
  117.  
  118.         if(it == lectures[curr_freq].end()){
  119.             ok = false;
  120.             break;
  121.         }
  122.         ans.emplace_back(*it);
  123.         int id = *it;
  124.         lectures[curr_freq].erase(it);
  125.  
  126.         if(curr_freq > 1){
  127.             pq.push(curr_freq - 1);
  128.             lectures[curr_freq - 1].emplace(id);
  129.         }
  130.     }
  131.  
  132.     if(not ok)
  133.         return void(cout << -1);
  134.  
  135.     cout << ans;
  136. }
  137.  
  138. void set_file(string& file_name){
  139.     freopen((file_name + ".in").c_str(), "r", stdin);
  140.     freopen((file_name + ".out").c_str(), "w", stdout);
  141. }
  142.  
  143. int main(){
  144.     Start_Crushing();
  145.  
  146. //    string file_name = "mex";
  147. //    set_file(file_name);
  148.  
  149.     int t = 1;
  150. //    /*Multiple test cases?*/ cin >> t;
  151.     while (t--) {
  152.         solve();
  153.         if(!t)
  154.             break;
  155.         cout << nl;
  156.     }
  157.  
  158. //    for(int tc = 1; tc <= t; tc++){
  159. //        cout << "Case " << tc << ":\n";
  160. //        solve();
  161. ////        if(tc != t)
  162. //            cout << nl;
  163. //    }
  164.  
  165.     return 0;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement