Submission #10183913


Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(), a.end()
#define reset(f, x) memset(f, x, sizeof(f))

typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1e5 + 5;
int n, a[N], ans[N], deg[N];

main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	cin >> n;
	set<int> s;
	for(int i=1; i<=n; ++i) s.insert(i);
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i <= n; ++i) deg[a[i]]++;
	set<ii> p;
	for(int i = 1; i <= n; ++i) p.insert(make_pair(deg[i],i));
	for(int i=1; i<=n; ++i){
		if(n-i+1<=10){
			//brute;
			vector<int> c;
			for(auto v:s) c.pb(v);
			do{
				bool ok=1;
				for(int j=0; j<(int)c.size()-1; ++j){
					if(a[c[j]]==c[j+1]){
						ok=0;
						break;
					}
				}
				if(a[ans[i-1]]==c[0]) ok=0;
				if(ok){
					for(int j=0; j<c.size(); ++j){
						ans[i+j]=c[j];
					}
					break;
				}
			}while(next_permutation(all(c)));
		}
		set<ii>::iterator u=p.end(); u--;
		if((*u).fi==n-i){
			ans[i]=(*u).se;
			if(a[ans[i-1]]==ans[i]) return cout<<-1,0;
		}
		else{
			set<int>::iterator u=s.begin();
			if(*u==a[ans[i-1]]){
				u++;
				if(u==s.end()) return cout<<-1,0;
			}
			ans[i]=*u;
		}
		s.erase(ans[i]);
		p.erase(make_pair(deg[ans[i]],ans[i]));
		int v=a[ans[i]];
		if(s.find(v) != s.end()){
			p.erase(make_pair(deg[v],v));
			p.insert(make_pair(deg[v]-1,v));
			deg[v]--;
		}
	}
	for(int i=1; i<=n; ++i) cout<<ans[i]<<' ';
}

Submission Info

Submission Time
Task D - Arrangement
User MemoryLand
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1759 Byte
Status WA
Exec Time 112 ms
Memory 11392 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 3
AC × 44
WA × 6
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 100 ms 11008 KB
hand2_04 AC 101 ms 11008 KB
hand_01 AC 1 ms 256 KB
hand_02 WA 1 ms 256 KB
hand_03 WA 111 ms 10752 KB
hand_04 WA 112 ms 10752 KB
handmaid_01 WA 1 ms 256 KB
max_01 AC 89 ms 11392 KB
max_02 AC 88 ms 11392 KB
max_03 AC 85 ms 11264 KB
max_04 AC 88 ms 11392 KB
max_05 AC 77 ms 11008 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 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 2 ms 256 KB
small_01 AC 4 ms 256 KB
small_02 AC 2 ms 256 KB
small_03 WA 1 ms 256 KB
small_04 AC 1 ms 256 KB
small_05 AC 2 ms 256 KB
special2_01 AC 78 ms 11008 KB
special2_02 AC 83 ms 11008 KB
special2_03 AC 79 ms 11008 KB
special2_04 AC 81 ms 11008 KB
special2_05 AC 95 ms 11008 KB
special2_06 AC 83 ms 11392 KB
special2_07 AC 82 ms 11392 KB
special2_08 AC 72 ms 11392 KB
special2_09 AC 81 ms 11392 KB
special2_10 AC 80 ms 11392 KB
special_01 AC 1 ms 256 KB
special_02 AC 4 ms 896 KB
special_03 AC 92 ms 11392 KB