Submission #70832875

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

vector<int> sq(vector<int> a) {
  int n = a.size();
  vector<int> res(n);
  for (int i = 0; i < n; i++) {
    res[i] = a[a[i]];
  }
  return res;
}

vector<int> brute(vector<int> a) {
  int n = a.size();
  vector<int> ans(n, n-1);
  auto dfs = [&] (this auto dfs, int i) {
    if (i == n) {
      ans = min(ans, sq(a));
      return;
    }
    if (a[i] != -1) dfs(i+1);
    else {
      for (int x = 0; x < n; x++) {
        a[i] = x;
        dfs(i+1);
      }
      a[i] = -1;
    }
  };
  dfs(0);
  return ans;
}

vector<int> solve(vector<int> a) {
  vector<int> oa = a;
  int n = a.size();
  if (a[0] <= 0) {
    for (auto& x: a) {
      if (x == -1) x = 0;
    }
    return sq(a);
  }

  int idx = n;
  set<int> pos;
  for (int i = 0; i < n; i++) {
    if (a[i] == 0) idx = min(idx, i);
    if (a[i] == -1) {
      pos.emplace(i);
    }
  }
  if (pos.empty()) return sq(a);

  auto finalize = [&] (vector<int> p, int f) -> vector<int> {
    // cout << "Finalizing with ";
    // for (int x: p) cout << x << ' ';
    // cout << "and " << f << "\n";
    if (p.empty()) {
      // for (auto& x: a) cout << x << ' ';
      // cout << "\n";
      // cout << f << '\n';
      pair<int, int> best = {n-1, n-1};
      for (int i = 0; i < n; i++) {
        if (i != f) {
          best = min(best, make_pair(a[i], i));
        }
      }
      best = min(best, make_pair(f, f));
      // cout << "Best is " << best.second << "\n";
      a[f] = best.second;
      vector<int> res = sq(a);
      a[f] = 0;
      res = min(res, sq(a));
      return res;
    }

    vector<int> b = a;
    for (int x: p) b[x] = f;
    b[f] = 0;
    vector<int> res = sq(b);
    if (idx < n) {
      for (int x: p) b[x] = idx;
      b[f] = idx;
      res = min(res, sq(b));
      b[f] = 0;
      res = min(res, sq(b));
    }
    return res;
  };

  vector<int> queued;
  vector<int> in_queue(n);
  for (int i = 0; i < n; i++) {
    // cout << "i = " << i << ' ' << a[i] << "\n";
    // for (auto x: a) cout << x << ' ';
    // cout << "\n";
    // for (int x: queued) cout << x << ' ';
    // cout << "\n";
    // cout << "pos size = " << pos.size() << "\n";
    if (a[i] != -1 && a[a[i]] == -1) {
      if (!in_queue[a[i]]) {
        if (pos.size() == 1) return finalize(queued, a[i]);
        a[a[i]] = 0;
        idx = min(idx, a[i]);
        pos.erase(a[i]);
        continue;
      }
      int v = *pos.lower_bound(i);
      if (v == *pos.rbegin()) {
        return finalize(queued, v);
      }
      v = min(v, idx);
      a[v] = 0;
      pos.erase(v);
      idx = min(idx, v);
      for (int x: queued) {
        a[x] = v;
        in_queue[x] = 0;
        pos.erase(x);
      }
      queued.clear();
    }
    else if (a[i] == -1) {
      // cout << "Visiting " << i << "\n";
      if (i == *pos.rbegin()) {
        return finalize(queued, i);
      }
      else {
        pos.erase(i);
        queued.push_back(i);
        in_queue[i] = 1;
      }
    }
  }
  if (count(a.begin(), a.end(), -1) != 0) {
    cout << "Error\n";
    for (auto x: oa) cout << x << ' ';
    cout << '\n';
    exit(0);
  }
  return sq(a);
}

int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  // vector<int> res = solve({2, -1, 1, -1, -1, 6, -1});
  // for (auto x: res) cout << x << ' ';
  // cout << '\n';
  // return 0;

  // for (int n = 1; n <= 8; n++) {
  //   vector<int> cur;
  //   auto dfs = [&] (this auto dfs) {
  //     if ((int)cur.size() == n) {
  //       auto res1 = brute(cur);
  //       auto res2 = solve(cur);
  //       if (res1 != res2) {
  //         cout << "Mismatch on ";
  //         for (auto x: cur) cout << x << ' ';
  //         cout << "\n";
  //         cout << "Brute: ";
  //         for (auto x: res1) cout << x << ' ';
  //         cout << "\n";
  //         cout << "Solve: ";
  //         for (auto x: res2) cout << x << ' ';
  //         cout << "\n";
  //         exit(0);
  //       }
  //       return;
  //     }
  //     for (int x = -1; x < n; x++) {
  //       if (x == -1 && count(cur.begin(), cur.end(), -1) >= 3) continue;
  //       cur.push_back(x);
  //       dfs();
  //       cur.pop_back();
  //     }
  //   };
  //   dfs();
  // }

  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x: a) {
      cin >> x;
      if (x != -1) x--;
    }
    vector<int> res = solve(a);
    for (int i = 0; i < n; i++) {
      cout << res[i]+1 << " \n"[i==n-1];
    }
  }
}

Submission Info

Judge Result