Submission #21441503
Source Code Expand
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <bits/stdc++.h>
using namespace std;
// 0-indexed
template <class T>
struct SegmentTree {
// a,b,c: T, e:T(unit)
// abc = (ab)c = a(bc)
// ae = ea = a
typedef function<T(T, T)> F;
int n;
F f;
T unit;
vector<T> dat;
SegmentTree(){};
SegmentTree(int newn, F f, T t) : f(f), unit(t) { init(newn); }
SegmentTree(const vector<T> &v, F f, T t) : f(f), unit(t) {
int _n = v.size();
init(v.size());
for (int i = 0; i < _n; ++i) dat[n + i] = v[i];
for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
}
void init(int newn) {
n = 1;
while (n < newn) n <<= 1;
dat.assign(n << 1, unit);
}
// "go up" process
void update(int k, T newdata) {
dat[k += n] = newdata;
while (k >>= 1) dat[k] = f(dat[k << 1], dat[(k << 1) | 1]);
}
// [a,b)
T query(int a, int b) {
T vl = unit, vr = unit;
for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
if (l & 1) vl = f(vl, dat[l++]);
if (r & 1) vr = f(dat[--r], vr);
}
return f(vl, vr);
}
// require: func(unit) == false
// min left: st <= res && func(seg.query(st,res + 1))
template <typename C>
int find_left(int st, C &func, T &acc, int k, int l, int r) {
if (l + 1 == r) {
acc = f(acc, dat[k]);
return func(acc) ? l : -1;
}
int mid = (l + r) >> 1;
if (mid <= st) return find_left(st, func, acc, (k << 1) | 1, mid, r);
if (st <= l && !func(f(acc, dat[k]))) {
acc = f(acc, dat[k]);
return -1;
}
int nres = find_left(st, func, acc, (k << 1), l, mid);
if (~nres) return nres;
return find_left(st, func, acc, (k << 1) | 1, mid, r);
}
template <typename C>
int find_left(int st, C &func) {
T acc = unit;
return find_left(st, func, acc, 1, 0, n);
}
// max right: res <= st && func(seg.query(res - 1,st))
template <typename C>
int find_right(int st, C &func, T &acc, int k, int l, int r) {
if (l + 1 == r) {
acc = f(dat[k], acc);
return func(acc) ? r : -1;
}
int mid = (l + r) >> 1;
if (st <= mid) return find_right(st, func, acc, k << 1, l, mid);
if (r <= st && !func(f(dat[k], acc))) {
acc = f(dat[k], acc);
return -1;
}
int nres = find_right(st, func, acc, (k << 1) | 1, mid, r);
if (~nres) return nres;
return find_right(st, func, acc, k << 1, l, mid);
}
template <typename C>
int find_right(int st, C &func) {
T acc = unit;
return find_right(st, func, acc, 1, 0, n);
}
};
using P = pair<int, int>;
int n;
vector<int> a;
SegmentTree<P> seg;
vector<int> solve();
int main() {
cin >> n;
a.assign(n + 1, -1);
for (int i = 1; i <= n; ++i) cin >> a[i];
auto res = solve();
if (res.size())
for (int i = 1; i <= n; ++i) cout << res[i] << " \n"[i == n];
else
cout << -1 << endl;
return 0;
}
vector<int> solve() {
{
auto f = [](P l, P r) { return max(l, r); };
vector<P> v(n + 1, P(0, 0));
for (int i = 1; i <= n; ++i) ++v[a[i]].first, v[i].second = i;
seg = SegmentTree<P>(v, f, P(0, 0));
}
vector<int> res(1, 0);
set<int> st;
for (int i = 1; i <= n; ++i) st.insert(i);
auto push = [&](int id) {
res.push_back(id);
st.erase(id);
int to = a[id];
auto now = seg.query(to, to + 1);
--now.first;
seg.update(to, now);
};
while (st.size() > 3) {
{ // corner pattern
int rem = n - res.size();
auto [cnt, id] = seg.query(0, n + 1);
if (cnt == rem) {
push(id);
continue;
}
}
for (auto id : st)
if (a[res.back()] != id) {
push(id);
break;
}
}
{ // all search
vector<int> v;
int len = st.size();
for (auto p : st) v.push_back(p);
do {
bool ch = 1;
for (int i = 0; i < len; ++i) {
if (a[res.back()] == v[i]) ch = 0;
res.push_back(v[i]);
}
if (ch) return res;
for (int i = 0; i < len; ++i) res.pop_back();
} while (next_permutation(v.begin(), v.end()));
}
return vector<int>();
}
Submission Info
Submission Time |
|
Task |
D - Arrangement |
User |
m_tsubasa |
Language |
C++ (GCC 9.2.1) |
Score |
800 |
Code Size |
4183 Byte |
Status |
AC |
Exec Time |
100 ms |
Memory |
10324 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
800 / 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 |
3 ms |
3480 KB |
hand2_02 |
AC |
2 ms |
3564 KB |
hand2_03 |
AC |
79 ms |
10180 KB |
hand2_04 |
AC |
84 ms |
10264 KB |
hand_01 |
AC |
4 ms |
3560 KB |
hand_02 |
AC |
2 ms |
3584 KB |
hand_03 |
AC |
100 ms |
10320 KB |
hand_04 |
AC |
91 ms |
10100 KB |
handmaid_01 |
AC |
8 ms |
3484 KB |
max_01 |
AC |
86 ms |
10324 KB |
max_02 |
AC |
87 ms |
10224 KB |
max_03 |
AC |
85 ms |
10152 KB |
max_04 |
AC |
86 ms |
10260 KB |
max_05 |
AC |
82 ms |
10152 KB |
random_01 |
AC |
4 ms |
3508 KB |
random_02 |
AC |
3 ms |
3416 KB |
random_03 |
AC |
2 ms |
3536 KB |
random_04 |
AC |
2 ms |
3416 KB |
random_05 |
AC |
2 ms |
3616 KB |
random_06 |
AC |
2 ms |
3612 KB |
random_07 |
AC |
2 ms |
3404 KB |
random_08 |
AC |
2 ms |
3616 KB |
random_09 |
AC |
2 ms |
3412 KB |
random_10 |
AC |
2 ms |
3628 KB |
random_11 |
AC |
1 ms |
3588 KB |
random_12 |
AC |
2 ms |
3424 KB |
random_13 |
AC |
2 ms |
3404 KB |
random_14 |
AC |
3 ms |
3580 KB |
random_15 |
AC |
5 ms |
3584 KB |
sample_01 |
AC |
2 ms |
3540 KB |
sample_02 |
AC |
3 ms |
3412 KB |
sample_03 |
AC |
2 ms |
3416 KB |
small_01 |
AC |
2 ms |
3584 KB |
small_02 |
AC |
2 ms |
3512 KB |
small_03 |
AC |
2 ms |
3612 KB |
small_04 |
AC |
2 ms |
3536 KB |
small_05 |
AC |
2 ms |
3456 KB |
special2_01 |
AC |
81 ms |
10256 KB |
special2_02 |
AC |
84 ms |
10156 KB |
special2_03 |
AC |
84 ms |
10152 KB |
special2_04 |
AC |
83 ms |
10096 KB |
special2_05 |
AC |
78 ms |
10072 KB |
special2_06 |
AC |
87 ms |
10152 KB |
special2_07 |
AC |
83 ms |
10220 KB |
special2_08 |
AC |
85 ms |
10180 KB |
special2_09 |
AC |
83 ms |
10256 KB |
special2_10 |
AC |
79 ms |
10224 KB |
special_01 |
AC |
2 ms |
3620 KB |
special_02 |
AC |
9 ms |
3888 KB |
special_03 |
AC |
93 ms |
10180 KB |