Submission #21441503


Source Code Expand

Copy
#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]);
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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
AC × 3
AC × 50
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


2025-02-28 (Fri)
22:46:19 +00:00