結果

問題 No.1635 Let’s Sort Integers!!
ユーザー logxlogx
提出日時 2021-07-23 19:10:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 118 ms / 2,000 ms
コード長 6,930 bytes
コンパイル時間 2,520 ms
コンパイル使用メモリ 215,216 KB
実行使用メモリ 15,472 KB
最終ジャッジ日時 2024-09-15 22:12:29
合計ジャッジ時間 18,112 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 3 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 2 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 2 ms
5,376 KB
testcase_46 AC 2 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 2 ms
5,376 KB
testcase_49 AC 2 ms
5,376 KB
testcase_50 AC 2 ms
5,376 KB
testcase_51 AC 2 ms
5,376 KB
testcase_52 AC 2 ms
5,376 KB
testcase_53 AC 3 ms
5,376 KB
testcase_54 AC 3 ms
5,376 KB
testcase_55 AC 2 ms
5,376 KB
testcase_56 AC 2 ms
5,376 KB
testcase_57 AC 2 ms
5,376 KB
testcase_58 AC 2 ms
5,376 KB
testcase_59 AC 2 ms
5,376 KB
testcase_60 AC 89 ms
7,632 KB
testcase_61 AC 96 ms
11,980 KB
testcase_62 AC 100 ms
15,472 KB
testcase_63 AC 96 ms
11,340 KB
testcase_64 AC 95 ms
10,956 KB
testcase_65 AC 93 ms
11,328 KB
testcase_66 AC 93 ms
11,376 KB
testcase_67 AC 94 ms
11,328 KB
testcase_68 AC 2 ms
5,376 KB
testcase_69 AC 2 ms
5,376 KB
testcase_70 AC 88 ms
7,500 KB
testcase_71 AC 98 ms
12,876 KB
testcase_72 AC 95 ms
10,956 KB
testcase_73 AC 92 ms
9,288 KB
testcase_74 AC 101 ms
15,028 KB
testcase_75 AC 94 ms
11,308 KB
testcase_76 AC 94 ms
11,372 KB
testcase_77 AC 118 ms
11,300 KB
testcase_78 AC 2 ms
5,376 KB
testcase_79 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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{
        int mid_or_left=(N-1)/2;
        al_use[mid_or_left]=al_use[mid_or_left+k]=true;
        ans[0]=mid_or_left+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++){
            dbg(ans);
            dbg(sec.size());
            //ans[i+1]を決める
            if(N&1 && ans[i]==mid_or_left){
                if(i==0 || ans[i-1]<=mid_or_left){
                    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]<=mid_or_left){
                    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]=mid_or_left;
    }
    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){
            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-(ans.back()==l-1);
            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