Submission #10183816
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){ 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 | 1370 Byte |
Status | WA |
Exec Time | 122 ms |
Memory | 11392 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 | 97 ms | 11008 KB |
hand2_04 | AC | 100 ms | 11008 KB |
hand_01 | AC | 1 ms | 256 KB |
hand_02 | WA | 1 ms | 256 KB |
hand_03 | WA | 119 ms | 10752 KB |
hand_04 | WA | 122 ms | 10752 KB |
handmaid_01 | WA | 1 ms | 256 KB |
max_01 | AC | 90 ms | 11392 KB |
max_02 | AC | 88 ms | 11392 KB |
max_03 | AC | 86 ms | 11264 KB |
max_04 | AC | 88 ms | 11392 KB |
max_05 | AC | 75 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 | 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 | 77 ms | 11008 KB |
special2_02 | AC | 80 ms | 11008 KB |
special2_03 | AC | 77 ms | 11008 KB |
special2_04 | AC | 81 ms | 11008 KB |
special2_05 | AC | 94 ms | 11008 KB |
special2_06 | AC | 88 ms | 11392 KB |
special2_07 | AC | 86 ms | 11392 KB |
special2_08 | AC | 73 ms | 11392 KB |
special2_09 | AC | 85 ms | 11392 KB |
special2_10 | AC | 82 ms | 11392 KB |
special_01 | AC | 1 ms | 256 KB |
special_02 | AC | 4 ms | 768 KB |
special_03 | AC | 92 ms | 11392 KB |