Submission #10182819
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int hmt() {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';if(n) x=-x;return x;}
#define in hmt()
#define ins ({string x;char c=getchar();for(;c==' '||c=='\n';c=getchar());for(;c!=' '&&c!='\n';c=getchar()) x+=c;x;})
#define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forb(i,BS) for(int i=BS._Find_first();i< BS.size();i = BS._Find_next(i))
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#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 onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
const int N=100010;
int n,x[N],s[N],a[N];
set<int> f;
set<pii> t;
void duyet(int i,int p)
{
if(i==n+1)
{
forinc(j,1,n) cout<<x[j]<<" ";
exit(0);
}
if(t.rbegin()->fi==n-i)
{
int u=t.rbegin()->se;
x[i]=u;
f.erase(u);
t.erase({s[u],u});
t.erase({s[a[u]],a[u]});
s[a[u]]--;
t.insert({s[a[u]],a[u]});
duyet(i+1,u);
f.insert(u);
t.erase({s[a[u]],a[u]});
s[a[u]]++;
t.insert({s[u],u});
t.insert({s[a[u]],a[u]});
}
else
{
forv(u,f) if(a[p]!=u)
{
x[i]=u;
f.erase(u);
t.erase({s[u],u});
t.erase({s[a[u]],a[u]});
s[a[u]]--;
t.insert({s[a[u]],a[u]});
duyet(i+1,u);
f.insert(u);
t.erase({s[a[u]],a[u]});
s[a[u]]++;
t.insert({s[u],u});
t.insert({s[a[u]],a[u]});
}
}
}
int main()
{
//freopen("ATCODER.inp","r",stdin);
n=in;
forinc(i,1,n) a[i]=in,f.insert(i),s[a[i]]++;
forinc(i,1,n) t.insert({s[i],i});
if(n==2&&a[1]==2) return cout<<-1,0;
duyet(1,0);
}
Submission Info
Submission Time |
|
Task |
D - Arrangement |
User |
tduong0806 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2106 Byte |
Status |
WA |
Exec Time |
147 ms |
Memory |
19200 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 |
118 ms |
18816 KB |
hand2_04 |
AC |
116 ms |
18816 KB |
hand_01 |
AC |
1 ms |
256 KB |
hand_02 |
WA |
1 ms |
256 KB |
hand_03 |
WA |
142 ms |
19200 KB |
hand_04 |
WA |
147 ms |
19200 KB |
handmaid_01 |
WA |
1 ms |
256 KB |
max_01 |
AC |
114 ms |
19200 KB |
max_02 |
AC |
101 ms |
19200 KB |
max_03 |
AC |
102 ms |
19072 KB |
max_04 |
AC |
104 ms |
19200 KB |
max_05 |
AC |
99 ms |
18816 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 |
WA |
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 |
WA |
1 ms |
256 KB |
random_12 |
AC |
1 ms |
256 KB |
random_13 |
AC |
1 ms |
256 KB |
random_14 |
WA |
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 |
WA |
1 ms |
256 KB |
small_04 |
AC |
1 ms |
256 KB |
small_05 |
AC |
1 ms |
256 KB |
special2_01 |
AC |
110 ms |
18816 KB |
special2_02 |
AC |
111 ms |
18816 KB |
special2_03 |
AC |
112 ms |
18816 KB |
special2_04 |
AC |
111 ms |
18816 KB |
special2_05 |
AC |
113 ms |
18816 KB |
special2_06 |
AC |
86 ms |
19200 KB |
special2_07 |
AC |
90 ms |
19200 KB |
special2_08 |
AC |
85 ms |
19200 KB |
special2_09 |
AC |
86 ms |
19200 KB |
special2_10 |
AC |
86 ms |
19200 KB |
special_01 |
AC |
1 ms |
256 KB |
special_02 |
AC |
4 ms |
1152 KB |
special_03 |
AC |
90 ms |
19200 KB |