結果
| 問題 | No.1635 Let’s Sort Integers!! |
| ユーザー |
 logx
|
| 提出日時 | 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()];
}