Submission #10183694
Source Code Expand
#include<bits/stdc++.h>
#define int ll
//{ PXH612
using namespace std;
#define ll long long
#define pp pair<int,int>
#define x first
#define y second
#define in ({ll x=0;int o=0,c=char();for(;!isdigit(c);c=getchar()) o=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';o?-x:x;})
#define inchar ({char c=getchar();while(c==' '||c=='\n') c=getchar();c;})
auto min(auto a,auto b){return a<b?a:b;}
auto max(auto a,auto b){return a>b?a:b;}
bool Min(auto &a,auto b) {if(a>b) {a=b;return true;}return false;}
bool Max(auto &a,auto b) {if(a<b) {a=b;return true;}return false;}
#define FOR(i,a,b) for(int i=a,_=b;i<=_;i++)
#define ROF(i,a,b) for(int i=b,_=a;_<=i;i--)
#define RR(x,a,b) {cout<<#x<<": ";FOR(__,a,b) cout<<x[__]<<" ";cout<<"\n";}
#define rr(x) " "<<#x<<'='<<x<<" "
#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define bitnum(x) __builtin_popcountll(x)
#define mu(x) (1ll<<x)
#define VEC(i,a) for(auto&i:a)
#define pb push_back
#define vn(a) (int)a.size()-1
#define false(x) if(!(x))
#define midd(a,b) (a+(b-(a))/2)
#define open(x) freopen(x,"r",stdin)
#define shut(x) freopen(x,"w",stdout)
//}//////////////////////////////////////////
const int N=1e5+5;
int n;
int a[N],cnt[N];
int d[N],ans[N];
priority_queue<int,vector<int>,greater<int>> h;
priority_queue<pp> hc;
void CHOOSE(int i,int x)
{
ans[i]=x;
cnt[a[x]]--;
d[x]=1;
}
main()
{
// open("arrange.inp");
n=in;int TK=min(n,10);
FOR(i,1,n) a[i]=in;
FOR(i,1,n) cnt[a[i]]++;
FOR(i,1,n) h.push(i);
FOR(i,1,n) hc.push({cnt[i],i});
FOR(id,1,n-TK)
{
while(hc.size())
{
int x=hc.top().y;
if(hc.top().x != cnt[x])
{
hc.pop();
hc.push({cnt[x],x});
}
else if(d[x]==1) hc.pop();
else break;
}
while(h.size()&&d[h.top()]==1) h.pop();
if(hc.size()&&hc.top().x==n-id) CHOOSE(id,hc.top().y);
else
{
int x=h.top();h.pop();
int y=h.top();h.pop();
if(a[ans[id-1]]==x) CHOOSE(id,y),h.push(x);
else CHOOSE(id,x),h.push(y);
}
}
vector<int> v;
FOR(i,1,n) if(d[i]==0) v.pb(i);
sort(v.begin(),v.end());
FOR(i,1,n-TK) cout<<ans[i]<<" ";
do
{
int ok=1;
if(a[ans[n-TK]]==v.front()) ok=0;
FOR(i,1,vn(v)) if(a[v[i-1]]==v[i]) ok=0;
if(ok==0) continue;
//FOR(i,1,vn(v)) cout<<rr(v[i-1]) rr(a[v[i-1]]) rr(v[i]) "\n";
VEC(i,v) cout<<i<<" ";break;
}
while(next_permutation(v.begin(),v.end()));
cout<<-1;
}
Submission Info
Submission Time |
|
Task |
D - Arrangement |
User |
pxh612 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2752 Byte |
Status |
WA |
Exec Time |
48 ms |
Memory |
6384 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 |
WA |
1 ms |
256 KB |
hand2_02 |
WA |
1 ms |
256 KB |
hand2_03 |
WA |
36 ms |
5616 KB |
hand2_04 |
WA |
37 ms |
5616 KB |
hand_01 |
WA |
1 ms |
256 KB |
hand_02 |
WA |
1 ms |
256 KB |
hand_03 |
WA |
40 ms |
6384 KB |
hand_04 |
WA |
40 ms |
6384 KB |
handmaid_01 |
WA |
1 ms |
256 KB |
max_01 |
WA |
48 ms |
6384 KB |
max_02 |
WA |
46 ms |
6384 KB |
max_03 |
WA |
43 ms |
6128 KB |
max_04 |
WA |
47 ms |
6384 KB |
max_05 |
WA |
36 ms |
5744 KB |
random_01 |
WA |
1 ms |
256 KB |
random_02 |
WA |
1 ms |
256 KB |
random_03 |
WA |
1 ms |
256 KB |
random_04 |
WA |
1 ms |
256 KB |
random_05 |
WA |
1 ms |
256 KB |
random_06 |
WA |
1 ms |
256 KB |
random_07 |
WA |
1 ms |
256 KB |
random_08 |
WA |
1 ms |
256 KB |
random_09 |
WA |
1 ms |
256 KB |
random_10 |
WA |
1 ms |
256 KB |
random_11 |
WA |
1 ms |
256 KB |
random_12 |
WA |
1 ms |
256 KB |
random_13 |
WA |
1 ms |
256 KB |
random_14 |
WA |
1 ms |
256 KB |
random_15 |
WA |
1 ms |
256 KB |
sample_01 |
WA |
1 ms |
256 KB |
sample_02 |
AC |
1 ms |
256 KB |
sample_03 |
WA |
2 ms |
256 KB |
small_01 |
WA |
5 ms |
256 KB |
small_02 |
WA |
2 ms |
256 KB |
small_03 |
WA |
1 ms |
256 KB |
small_04 |
WA |
1 ms |
256 KB |
small_05 |
WA |
2 ms |
256 KB |
special2_01 |
WA |
36 ms |
5616 KB |
special2_02 |
WA |
36 ms |
5616 KB |
special2_03 |
WA |
36 ms |
5616 KB |
special2_04 |
WA |
36 ms |
5616 KB |
special2_05 |
WA |
36 ms |
5616 KB |
special2_06 |
WA |
36 ms |
6384 KB |
special2_07 |
WA |
36 ms |
6384 KB |
special2_08 |
WA |
35 ms |
6384 KB |
special2_09 |
WA |
36 ms |
6384 KB |
special2_10 |
WA |
35 ms |
6384 KB |
special_01 |
WA |
1 ms |
256 KB |
special_02 |
WA |
3 ms |
640 KB |
special_03 |
WA |
34 ms |
6384 KB |