結果

問題 No.1635 Let’s Sort Integers!!
コンテスト
ユーザー logx
提出日時 2021-07-06 23:29:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 6,836 bytes
コンパイル時間 2,505 ms
コンパイル使用メモリ 208,320 KB
最終ジャッジ日時 2025-01-22 17:53:31
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 60 RE * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef LOGX
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;

/*---------macro---------*/
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define unless(x) if(!(x))
#define until(x) while(!(x))
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define mybit(i,j) (((i)>>(j))&1)

/*---------type/const---------*/
const int big=1000000007;
//const int big=998244353;
const double EPS=1e-8; //適宜変える
typedef long long ll;
typedef unsigned long long ull;
typedef std::string::const_iterator state; //構文解析
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const char newl='\n';
struct{
    constexpr operator int(){return -int(1e9)-10;}
    constexpr operator ll(){return -ll(1e18)-10;}
}neginf;
struct{
    constexpr operator int(){return int(1e9)+10;}
    constexpr operator ll(){return ll(1e18)+10;}
    constexpr auto operator -(){return neginf;}
}inf;

/*---------debug---------*/
#ifdef LOGX
#include <template/debug.hpp>
#else
#define dbg(...) ;
#define dbgnewl ;
#define prt(x) ;
#define _prt(x) ;
#endif

/*---------function---------*/
template<typename T> T max(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=max(ans,elem);}return ans;}
template<typename T> T min(const std::vector<T> &a){T ans=a[0];for(T elem:a){ans=min(ans,elem);}return ans;}
template<typename T,typename U> bool chmin(T &a,const U b){if(a>b){a=b;return true;}return false;}
template<typename T,typename U> bool chmax(T &a,const U b){if(a<b){a=b;return true;}return false;}
bool valid(int i,int j,int h,int w){return (i>=0 && j>=0 && i<h && j<w);}
template<class T,class U>T expm(T x,U y,const ll mod=big){T res=1;while(y){if(y&1)(res*=x)%=mod;(x*=x)%=mod;y>>=1;}return res;}
template<class T,class U>T exp(T x,U y){T res=1;while(y){if(y&1)res*=x;x*=x;y>>=1;}return res;}

//K=N*N/2-k に対する構成
//k>=[N/2]なら0を端にして組む
vector<int> solve(int N,int k){
    assert(1<=k && k<=N-1);
    dbg(N,k);

    vector<bool> al_use(N,false);
    vector<int> ans(N);
    if(N/2<=k && k<=N-1){
        al_use[0]=al_use[k]=true;
        ans[0]=0;
        stack<int> fir;
        stack<int> sec;
        for(int i=0;i*2<N;i++){
            fir.emplace(i);
        }
        for(int i=N/2;i<N;i++){
            sec.emplace(i);
        }
        for(int i=0;i<N-2;i++){
            //ans[i+1]を決める
            if(N&1 && ans[i]==N/2){
                if(ans[i-1]<N/2){
                    while(al_use[sec.top()])sec.pop();
                    ans[i+1]=sec.top();
                    sec.pop();
                }
                else{
                    while(al_use[fir.top()])fir.pop();
                    ans[i+1]=fir.top();
                    fir.pop();
                }
                al_use[ans[i+1]]=true;
            }
            else{
                if(ans[i]<N/2){
                    while(al_use[sec.top()])sec.pop();
                    ans[i+1]=sec.top();
                    sec.pop();
                }
                else{
                    while(al_use[fir.top()])fir.pop();
                    ans[i+1]=fir.top();
                    fir.pop();
                }
                al_use[ans[i+1]]=true;
            }
        }
        ans[N-1]=k;
    }
    else{
        al_use[N/2]=al_use[N/2+k]=true;
        ans[0]=N/2+k;
        stack<int> fir;
        stack<int> sec;
        for(int i=0;i*2<N;i++){
            if(!al_use[i])fir.emplace(i);
        }
        for(int i=N/2;i<N;i++){
            if(!al_use[i])sec.emplace(i);
        }
        for(int i=0;i<N-2;i++){
            //ans[i+1]を決める
            if(N&1 && ans[i]==N/2){
                if(i==0 || ans[i-1]<N/2){
                    while(al_use[sec.top()])sec.pop();
                    ans[i+1]=sec.top();
                    sec.pop();
                }
                else{
                    while(al_use[fir.top()])fir.pop();
                    ans[i+1]=fir.top();
                    fir.pop();
                }
                al_use[ans[i+1]]=true;
            }
            else{
                if(ans[i]<N/2){
                    while(al_use[sec.top()])sec.pop();
                    ans[i+1]=sec.top();
                    sec.pop();
                }
                else{
                    if(ans[i]!=4)while(al_use[fir.top()])fir.pop();
                    ans[i+1]=fir.top();
                    fir.pop();
                }
                if(ans[i]!=4)al_use[ans[i+1]]=true;
            }
        }
        ans[N-1]=N/2;
    }
    return ans;
}

ll first_k;

void check(ll K,vector<int> a){
    for(int i=0;i<(int)a.size()-1;i++)K-=abs(a[i]-a[i+1]);
    cout << (K==0 ? "OK":"NG") << newl;
}

int main(){
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    std::cout.precision(10);
/*------------------------------------*/
    
    ll N,K;
    cin >> N >> K;

    first_k=K;

    if(K<N-1 || N*N/2-1<K){
        cout << -1 << newl;
        return 0;
    }
    ll k=N*N/2-K;
    if(1<=k && k<=N-1){
        auto ans=solve(N,k);
        for(int i=0;i<N;i++)cout << ans[i]+1 << " \n"[i+1==N];
        return 0;
    }
    vector<int> ans={(int)N-1};
    bool rev=true;
    int l=0,r=N-1;//[l,r)が残っている
    while(true){//あとN-1個決める。後ろN個でKを作る。
        k=N*N/2-K;
        assert(N/2<=k);
        if(N<=5){
            dbg('D');
            dbg(l,r);
            dbg(ans);
            vector<int> p(N);
            iota(p.begin(),p.end(),0);
            do{
                int sum=0;
                rep(i,N-1)sum+=abs(p[i]-p[i+1]);
                if(sum==K)break;
            }while(next_permutation(p.begin()+1,p.end()));
            if(rev)for(auto &x:p)x=N-1-x;
            for(auto &x:p)x+=l-(ans.back()==l-1);
            assert(p[0]==ans.back());
            ans.pop_back();
            for(auto x:p)ans.emplace_back(x);
            break;
        }
        else if(N/2<=k && k<=N-1){
            auto p=solve(N,k);
            if(rev)for(auto &x:p)x=N-1-x;
            for(auto &x:p)x+=l;
            assert(p[0]==ans.back());
            ans.pop_back();
            for(auto x:p)ans.emplace_back(x);
            //うまくansに加える
            break;
        }
        else if(K-1 <= (N-1)*(N-1)/2 - (N-1)/2){
            K--;
            N--;
            if(rev)ans.emplace_back(--r);
            else ans.emplace_back(l++);
        }
        else{
            K-=N-1;
            N--;
            rev=!rev;
            if(rev)ans.emplace_back(--r);
            else ans.emplace_back(l++);
        }
        dbg(N,K);
        assert(N-1<=K && K<=N*N/2-N/2);
    }

    //check(first_k,ans);
    rep(i,ans.size())cout << ans[i]+1 << " \n"[i+1==(int)ans.size()];
}
0