Codeforces Round #713 (Div. 3) E. Permutation by Sum（贪心）

本来手痒想自己开把div3练手来着，佬儿叫住我组队打，就换了这场，听说除了G数学，F也是模拟，其它的都是大模拟:)
模拟人可以狠狠冲，注意细节即可

https://codeforces.com/contest/1512/problem/E

题目大意：

给定四个整数n，l，r (1≤l≤r≤n)和s (1≤s≤n(n+1)2 ),要求找出一个满足下列条件的从1到n的数的排列p:

s=pl+pl+1+…+pr。

如果有几个合适的排列，打印其中任何一个；否则输出-1。 

input 
5
5 2 3 5
5 3 4 1
3 1 2 4
2 2 2 2
2 1 1 3
output 
1 2 3 4 5 
-1
1 3 2 
1 2 
-1

详解见代码内注释部分

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=1000200,M=2002;
//unordered_map<LL,LL> a[N];
//priority_queue<LL> pq;
//priority_queue<LL,vector<LL>,greater<LL>> pq2;
LL n,l,r,s;
LL a[N],sum[N];
void init()
{
    for(int i=1;i<=500;i++)
        sum[i]=sum[i-1]+i;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    init();
    while(T--)
    {
        cin>>n>>l>>r>>s;
        memset(a,0,sizeof a);
        bool flag=true;
        //cout<<n-(r-l)-1<<" "<<r-l+1<<endl;
        LL maxn=sum[n]-sum[n-(r-l)-1],minn=sum[r-l+1];
        if(maxn<s) flag=false;
        else if(minn>s) flag=false;
        else
        {
            //先把a[l-r]从1-n填满为止
            for(int i=l;i<=r;i++)
                a[i]=i-l+1;
            //for(int i=l;i<=r;i++)
            //    cout<<a[i]<<" ";
            //cout<<endl;
            map<LL,LL> mp;
            LL minn2=minn;
            for(int i=r;i>=l;i--)
            {
                LL need=min(s-minn2,n-a[i]-(r-i));
                //避免出界n-r+i-a[i]
                //a[i]到达n为最大距离，在仍需较大数时要保证后面已经填好的数依旧比自己大，即r-i为边长（一个一个依次递减）
                //cout<<s-minn2<<" "<<n-r+i-a[i]<<endl;
                a[i]+=need;
                minn2+=need;
                mp[a[i]]++;
            }
            //两边填满
            LL j=1;
            for(int i=1;i<l;i++)
            {
                while(j<=n&&mp[j]!=0) j++;
                if(j<=n)
                {
                    a[i]=j++;
                    mp[a[i]]++;
                }
            }
            for(int i=r+1;i<=n;i++)
            {
                while(j<=n&&mp[j]!=0) j++;
                if(j<=n)
                {
                    a[i]=j++;
                    mp[a[i]]++;
                }
            }
            for(int i=1;i<=n;i++)
                cout<<a[i]<<" ";
            cout<<endl;
            mp.clear();
        }
        if(flag==false) cout<<"-1"<<endl;
    }
    return 0;
}