[CF 1512E] Permutation by Sum

[CF 1512E] Permutation by Sum - 1600

 

문제 요약 : 

1~n수 중에서 (r-l+1)개 중복없이 뽑아서 s만들 수 있는지를 묻고 있다.

 

문제 풀이 : 

n부터 1씩 줄여나가면서 누적합을 쌓아가면서 s를 만든다. 이때 만들어진 수의 집합은 최소의 개수이므로 (r-l+1)개보다 적거나 같을 것이다. 만약 크다면 s를 만들 수 없다는 뜻이다. 

개수를 늘리기 위해서는 작은 값부터 2개로 쪼개면 된다. 예를 들어 x라는 값을 쪼갠다면 (1,x-1) 또는 (2,x-2) 또는 (3,x-3)...이런 식이다. 이때 쪼개진 결과로 나오는 두 개의 값은 초기 집합과 겹치면 안된다. 겹치지 않는 것이 확인이 된다면 set에서 두 값을 insert 해주고 원래 x값은 삭제해준다. 가장 작은 값부터 쪼개기 때문에 연속적으로 시행해도 계속 작아짐이 보장된다.

 

 

#include <bits/stdc++.h>
using namespace std;
/************************Contest Template**************************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
string exm;
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
template <typename T>
inline void showAll(vector<T> &v,string sep=""){
    for(T &here:v) cout<<here<<sep;}
template <typename T>
inline void showAll(T a[],int st,int end,string sep=""){
    for(int i=st ; i<=end ; i++) cout<<a[i]<<sep; }
template <typename T>
inline vector<int> int_seperation(T N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/************************Contest Template**************************/
const int SIZE=200009;

int main(){
    int t;  scanf("%d",&t);
    while(t--){
        int n,l,r,s;  scanf("%d %d %d %d",&n,&l,&r,&s);
        set<int> si;
        
        int mn = 0,mx = 0;
        for(int i=1 ; i<=r-l+1 ; i++){
            mn += i;
        }
        for(int i=n ; i>=n-(r-l+1)+1 ; i--){
            mx += i;
        }
        
        if(s>mx || s<mn) {
            printf("-1\n");
            continue;
        }
        
        for(int i=n,sum=0 ; i>=1 ; i--){
            if(sum + i <= s) {
                si.insert(i);
                sum += i;   
            }
        }
        
        auto it = si.begin();
        while(si.size() != r-l+1){
            int x = *it;
            int check = 0;
            for(int j=1 ; j<=x-1 ; j++){
                if(j!=x-j && si.count(j)==0 && si.count(x-j)==0){
                    si.erase(x);
                    si.insert(j);
                    si.insert(x-j);
                    check = 1;
                    it = si.begin();
                    break;
                }
            }
            if(!check) it = next(it);
        }
        
        int ans[509]={0};
        set<int> unused;
        for(int i=1 ; i<=n ; i++) unused.insert(i);
        for(int x : si){
            if(x > 0) unused.erase(x);
        }
        
        for(int i=1 ; i<=n ; i++){
            if(i>=l && i<=r){
                ans[i] = *si.begin();
                si.erase(ans[i]);
            }
            else {
                ans[i] = *unused.begin();
                unused.erase(ans[i]);
            }
        }
        
        set<int> test;
        for(int i=1 ; i<=n ; i++){
            if(test.count(ans[i])) assert(0);
            else test.insert(ans[i]);
        }

        showAll(ans,1,n," ");
        printf("\n");
    }
    
}