jainbot27

Untitled

Mar 27th, 2021
231
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define f first
  5. #define s second
  6. #define pb push_back
  7. #define ar array
  8. #define all(x) x.begin(), x.end()
  9. #define siz(x) (int)x.size()
  10.  
  11. #define FOR(x, y, z) for(int x = (y); x < (z); x++)
  12. #define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
  13. #define F0R(x, z) FOR(x, 0, z)
  14. #define R0F(x, z) ROF(x, 0, z)
  15. #define trav(x, y) for(auto&x:y)
  16.  
  17. using ll = long long;
  18. using vi = vector<int>;
  19. using vl = vector<long long>;
  20. using pii = pair<int, int>;
  21. using vpii = vector<pair<int, int>>;
  22.  
  23. template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
  24. template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
  25. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  26.  
  27. const char nl = '\n';
  28. const int mxN = 2e5 + 10;
  29. const int MOD = 1e9 + 7;
  30. const long long infLL = 1e18;
  31.  
  32. void solve(){
  33.     int n, k;
  34.     cin >> n >> k;
  35.     k -= n-1;
  36.     if(k>n*(n-1)/2||k<0){
  37.         cout << "IMPOSSIBLE\n";
  38.         return;
  39.     }
  40.     vi a(n, -1);
  41.     F0R(i, n){
  42.         if(k>n-i-1){
  43.             if(i%2==0){
  44.                 a[n-(i/2)-1] = i;
  45.             }
  46.             else{
  47.                 a[i/2] = i;
  48.             }
  49.             k -= n-i-1;
  50.         }
  51.         else{
  52.             if(i%2==0){
  53.                 a[n-(i/2)-1-((n-i-1)-k)] = i;
  54.             }
  55.             else{
  56.                 a[i/2+((n-i-1)-k)] = i;
  57.             }
  58.             int cnt = i+1;
  59.             int SP = -1;
  60.             bool seen = 0;
  61.             if(i%2==0){
  62.                 F0R(j, n){
  63.                     if(a[j]!=-1&&!seen) SP = j;
  64.                     if(a[j]==-1) a[j] = cnt++, seen = 1;
  65.                 }
  66.                 reverse(a.begin()+SP+1, a.begin()+n-(i/2)-1-((n-i-1)-k));
  67.             }
  68.             else{
  69.                 SP = n;
  70.                 R0F(j, n){
  71.                     if(a[j]!=-1&&!seen) SP=j;
  72.                     if(a[j]==-1) a[j] = cnt++, seen = 1;
  73.                 }
  74.                 reverse(a.begin()+i/2+((n-i-1)-k)+1, a.begin()+SP);
  75.             }
  76.             k = 0;
  77.  
  78.             break;
  79.         }
  80.     }
  81.     F0R(i, n){
  82.         cout << a[i]+1 <<  ' ';
  83.     }
  84.     cout << nl;
  85. }
  86.  
  87. int32_t main(){
  88.     ios_base::sync_with_stdio(0); cin.tie(0);
  89.     int t; cin >> t;
  90.     F0R(i, t){
  91.         cout << "Case #" << i+1 << ": ";
  92.         solve();
  93.     }
  94.  
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment