#673384 (C++17) No.1635 Let’s Sort Integers!!

提出ソース

結果

問題	No.1635 Let’s Sort Integers!!
ユーザー	logx
提出日時	2021-07-06 23:36:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	6,978 bytes
コンパイル時間	2,666 ms
コンパイル使用メモリ	215,280 KB
実行使用メモリ	15,360 KB
最終ジャッジ日時	2024-09-15 21:33:13
合計ジャッジ時間	8,887 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 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	RE	-
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	2 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	2 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	3 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	3 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	2 ms 5,376 KB
testcase_54	AC	2 ms 5,376 KB
testcase_55	AC	3 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	88 ms 7,504 KB
testcase_61	AC	103 ms 11,848 KB
testcase_62	AC	98 ms 15,360 KB
testcase_63	AC	94 ms 11,212 KB
testcase_64	AC	94 ms 10,956 KB
testcase_65	AC	94 ms 11,392 KB
testcase_66	AC	94 ms 11,392 KB
testcase_67	AC	94 ms 11,392 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	99 ms 12,876 KB
testcase_72	AC	95 ms 10,956 KB
testcase_73	AC	92 ms 9,292 KB
testcase_74	AC	102 ms 14,904 KB
testcase_75	AC	116 ms 11,520 KB
testcase_76	AC	94 ms 11,392 KB
testcase_77	AC	108 ms 11,392 KB
testcase_78	AC	2 ms 5,376 KB
testcase_79	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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){
            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()];
}

yukicoder

結果

テストケース

ソースコード