Advertisement
Ankit_132

E

Feb 7th, 2024
1,179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6.  
  7. void solve() {
  8.     int n, operations;
  9.     cin >> n >> operations;
  10.  
  11.     if (operations > ((n - 1) * (n - 1)) || operations < (((n - 1) * n) / 2)) {
  12.         cout << -1 << endl;
  13.     } else if (n == 1) {
  14.         cout << 1 << endl;
  15.     } else {
  16.         vector<int> result(n, 0);
  17.         result[0] = 1;
  18.  
  19.         vector<int> changes(n, 0);
  20.         for (int i = 1; i < n; i++) {
  21.             changes[i] = i;
  22.             operations -= i;
  23.         }
  24.  
  25.         int l = n - 2;
  26.         while (operations) {
  27.             int f = n - 1 - changes[l];
  28.             f = min(f, operations);
  29.             operations -= f;
  30.             changes[l] += f;
  31.             l--;
  32.         }
  33.  
  34.         int f = 0;
  35.         result[0] = 1;
  36.  
  37.         set<int> remaining, modifiedSet;
  38.         for (int i = 1; i <= n; i++) {
  39.             remaining.insert(i);
  40.             modifiedSet.insert(1 + changes[i - 1]);
  41.         }
  42.  
  43.         modifiedSet.erase(0);
  44.         while (!modifiedSet.empty()) {
  45.             remaining.erase(*modifiedSet.begin());
  46.             modifiedSet.erase(modifiedSet.begin());
  47.         }
  48.  
  49.         if (remaining.find(1) != remaining.end()) {
  50.             remaining.erase(1);
  51.         }
  52.  
  53.         for (int i = 1; i < n; i++) {
  54.             if (f == changes[i]) {
  55.                 result[i] = (*remaining.begin());
  56.                 remaining.erase(remaining.begin());
  57.             } else {
  58.                 f = changes[i];
  59.                 result[i] = 1 + f;
  60.             }
  61.         }
  62.  
  63.         for (int i = 0; i < n; i++) {
  64.             cout << result[i] << " ";
  65.         }
  66.         cout << endl;
  67.     }
  68. }
  69.  
  70. int32_t main() {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(NULL);
  73.  
  74.     int t;
  75.     cin >> t;
  76.  
  77.     while (t--)
  78.         solve();
  79.    
  80. }
  81.  
  82.  
  83.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement