• 欢迎光临~

Codeforces Round #713 E

开发技术 开发技术 2022-10-18 次浏览

E. Permutation by Sum

显然轻松上下界判断
考虑如何构造
我们将它整成最小的样子 1 2 3 4 ....k个
从后往前要是他需要我们就直接加上去就可以了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl 'n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);

void solve() {
    int n,l,r,s;cin>>n>>l>>r>>s;
    int len=r-l+1,d=0,u=0;
    vector<int>st(n+1);
    vector<int>v;
    for(int i=1;i<=len;i++)d+=i,v.push_back(i);
    for(int i=n;i>=n-len+1;i--)u+=i;
    if(d<=s&&s<=u){
        int now=d,need=(n-len);
        for(int i=len-1;i>=0;i--){
            if(now+need<s){
                v[i]+=need;
                now+=need;
            }else{
                v[i]+=s-now;
                break;
            }
        }
        for(int i=0;i<len;i++)st[v[i]]=1;
        vector<int>ans;
        for(int i=1;i<=n;i++){
            if(!st[i]){
                if(ans.size()==l-1)break;
                ans.push_back(i);
                st[i]=1;
            }
        }
        for(auto i:v)ans.push_back(i);
        for(int i=1;i<=n;i++){
            if(!st[i]){
                ans.push_back(i);
                st[i]=1;
            }
        }
        for(auto i:ans)cout<<i<<' ';cout<<endl;
    }else cout<<-1<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
    return ~~(0^_^0);
}
程序员灯塔
转载请注明原文链接:Codeforces Round #713 E
喜欢 (0)