Untitled

 avatar
unknown
plain_text
a year ago
1.6 kB
5
Indexable
#pragma GCC optimize("O2,no-stack-protector,unroll-loops")
#define ll long long
#define pb push_back
#define ipar(arr, n) vector<ll> arr(n); for(int i=0;i<n;i++) cin>>arr[i];
#include <cmath>
#include <bits/stdc++.h>
#define pii pair<int, int>;
#define pll pair<ll, ll>;
using namespace std;


void solve(){
    ll n,k;cin>>n>>k;
    ll ma=(n-1)*(n-1);
    ll mi=(n-1)*n/2;
    if(k<mi || k>ma){
        cout<<-1<<"\n";
        return;
    }
    
    //making difference array
    vector<ll>d(n);
    ll sum=0;
    for(ll i=1;i<=n;i++) {
        d[i-1]=i-1;
        sum+=d[i-1];
    }
    ll ind=n-1;
    while(sum<k && ind>=0){
        if(d[ind]==n-1) ind--;
        ll pos=min(k-sum,n-1-d[ind]);
        d[ind]+=pos;
        sum+=pos;
    }
    
   // for(int i=1;i<=n;i++) cout<<i<<" "; cout<<"\n";
   // for(auto i:d) cout<<i<<" ";
   // cout<<"\n";
    //making the perm array
    
    set<ll>used;
    vector<ll>perm(n,0);
    ll inin=-1;
    for(ll i=1;i<=n;i++){
        if(d[i-1]==i-1){
            perm[i-1]=i;
            used.insert(i);
        }else if(d[i-1]<n-1 && d[i-1]>i-1){
            perm[i-1]=d[i-1]+1;
            used.insert(d[i-1]+1);
        }else if(d[i-1]==n-1){
            perm[i-1]=n;
            used.insert(n);
            inin=i;
            break;
        }
    }
    for(ll i=1;i<=n;i++){
        if(used.find(i)==used.end()){
            perm[inin]=i;
            inin++;
            used.insert(i);
        }
    }
    for(auto i:perm) cout<<i<<" ";
    cout<<"\n";
    
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
	cin>>t;
	while(t--) solve();
}
Editor is loading...
Leave a Comment