Untitled
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