Untitled
unknown
plain_text
2 years ago
1.6 kB
6
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