Submission #10186871
Source Code Expand
/// https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d #include <bits/stdc++.h> using namespace std; #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;}) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rng(1); int rnd(int l,int r){return l+rng()%(r-l+1);} #define fasty ios_base::sync_with_stdio(0),cin.tie(0); #define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a) #define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a) #define forv(a,b) for(auto&a:b) #define fi first #define se second #define pb push_back #define ii pair<int,int> #define mt make_tuple #define all(a) a.begin(),a.end() #define reset(f, x) memset(f, x, sizeof(f)) #define bit(x,i) ((x>>(i-1))&1) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1<<(i-1))) #define gg exit(0); const int N=100010; int n; int cnt[N],a[N],b[N],dd[N],to[N]; priority_queue<ii> q; int root(int i){ return to[i]==i ? i : to[i]=root(to[i]); } main(){ #define task "arrangement" //freopen(task".inp","r",stdin); //freopen(task".out","w",stdout); if((n=in)==2) return cout<<-1,0; forinc(i,1,n) cnt[a[i]=in]++; forinc(i,1,n){ q.push({(n==100000) ? cnt[a[i]] : cnt[i],i}); to[i]=i; } to[n+1]=n+1; forinc(i,1,n-min(n,5)){ while(q.size() && (dd[q.top().se] || q.top().fi!=cnt[q.top().se])) q.pop(); if(q.size() && q.top().fi==n-i){ b[i]=q.top().se; to[q.top().se]=q.top().se+1; cnt[a[b[i]]]--; q.push({cnt[a[b[i]]],a[b[i]]}); dd[b[i]]=1; q.pop(); } else{ for(int j=root(1);j<=n;j=root(j+1)) if(j!=a[b[i-1]]){ dd[b[i]=j]=1; to[j]=j+1; break; } } } vector<int> lf; forinc(i,1,n) if(to[i]==i) lf.pb(i); int b4=b[n-min(n,5)]; do{ if(a[b4]==lf[0]) continue; int i=0; while(i<lf.size()-1 && a[lf[i]]!=lf[i+1]) i++; if(i==lf.size()-1){ forinc(j,1,n-min(n,5)) cout<<b[j]<<" "; forv(j,lf) cout<<j<<" "; gg } } while(next_permutation(all(lf))); }
Submission Info
Submission Time | |
---|---|
Task | D - Arrangement |
User | unx |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2344 Byte |
Status | WA |
Exec Time | 29 ms |
Memory | 3700 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 800 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01, sample_02, sample_03 |
All | hand2_01, hand2_02, hand2_03, hand2_04, hand_01, hand_02, hand_03, hand_04, handmaid_01, max_01, max_02, max_03, max_04, max_05, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, random_14, random_15, sample_01, sample_02, sample_03, small_01, small_02, small_03, small_04, small_05, special2_01, special2_02, special2_03, special2_04, special2_05, special2_06, special2_07, special2_08, special2_09, special2_10, special_01, special_02, special_03 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
hand2_01 | AC | 1 ms | 256 KB |
hand2_02 | AC | 1 ms | 256 KB |
hand2_03 | AC | 20 ms | 3316 KB |
hand2_04 | WA | 20 ms | 2676 KB |
hand_01 | AC | 1 ms | 256 KB |
hand_02 | AC | 1 ms | 256 KB |
hand_03 | AC | 20 ms | 3700 KB |
hand_04 | AC | 28 ms | 3700 KB |
handmaid_01 | AC | 1 ms | 256 KB |
max_01 | AC | 28 ms | 3700 KB |
max_02 | AC | 29 ms | 3700 KB |
max_03 | AC | 29 ms | 3572 KB |
max_04 | AC | 29 ms | 3700 KB |
max_05 | AC | 29 ms | 3316 KB |
random_01 | AC | 1 ms | 256 KB |
random_02 | AC | 1 ms | 256 KB |
random_03 | AC | 1 ms | 256 KB |
random_04 | AC | 1 ms | 256 KB |
random_05 | AC | 1 ms | 256 KB |
random_06 | AC | 1 ms | 256 KB |
random_07 | AC | 1 ms | 256 KB |
random_08 | AC | 1 ms | 256 KB |
random_09 | AC | 1 ms | 256 KB |
random_10 | AC | 1 ms | 256 KB |
random_11 | AC | 1 ms | 256 KB |
random_12 | AC | 1 ms | 256 KB |
random_13 | AC | 1 ms | 256 KB |
random_14 | AC | 1 ms | 256 KB |
random_15 | AC | 1 ms | 256 KB |
sample_01 | AC | 1 ms | 256 KB |
sample_02 | AC | 1 ms | 256 KB |
sample_03 | AC | 1 ms | 256 KB |
small_01 | AC | 1 ms | 256 KB |
small_02 | AC | 1 ms | 256 KB |
small_03 | AC | 1 ms | 256 KB |
small_04 | AC | 1 ms | 256 KB |
small_05 | AC | 1 ms | 256 KB |
special2_01 | WA | 20 ms | 2676 KB |
special2_02 | WA | 20 ms | 2676 KB |
special2_03 | WA | 20 ms | 2676 KB |
special2_04 | WA | 20 ms | 2676 KB |
special2_05 | WA | 20 ms | 2676 KB |
special2_06 | WA | 20 ms | 3060 KB |
special2_07 | WA | 21 ms | 3060 KB |
special2_08 | WA | 20 ms | 3060 KB |
special2_09 | WA | 21 ms | 3060 KB |
special2_10 | WA | 20 ms | 3060 KB |
special_01 | AC | 1 ms | 256 KB |
special_02 | AC | 2 ms | 512 KB |
special_03 | AC | 29 ms | 3700 KB |