結果
問題 | No.1635 Let’s Sort Integers!! |
ユーザー |
![]() |
提出日時 | 2021-07-23 19:10:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 6,930 bytes |
コンパイル時間 | 2,123 ms |
コンパイル使用メモリ | 210,324 KB |
最終ジャッジ日時 | 2025-01-23 07:42:28 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 77 |
ソースコード
#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()]; }