Submission #56424496

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<int> A;
  for (int i = 2; i <= N; i ++) {
    int a;
    cin >> a;
    A.push_back((N - i + a) % N);
  }
  sort(A.begin(), A.end());
  A.erase(unique(A.begin(), A.end()), A.end());
  int K = A.size();
  for (int i = 0; i < K * 2; i ++) {
    A.push_back(A[i] + N);
  }
  vector<int> ans(N, N);
  for (int i = 0; i < N; i ++) {
    int id = i + N;
    auto p1 = upper_bound(A.begin(), A.end(), id);
    auto pt = lower_bound(A.begin(), A.end(), id);
    auto p2 = prev(pt);
    int d = max(abs(id - *p1), abs(id - *p2));
    ans[i] = N - d;
  }
  /*
  for (int i = 0; i < N; i ++) {
    cout << ans[i] << " ";
  }
  cout << endl;
  */
  for (int i = 1; i < N * 5; i ++) {
    int p = i % N, q = (i - 1) % N;
    ans[p] = min(ans[p], ans[q] + 1);
  }
  for (int i = N * 5; i; i --) {
    int p = i % N, q = (i + 1) % N;
    ans[p] = min(ans[p], ans[q] + 1);
  }
  for (int i = 0; i < N; i ++) {
    cout << ans[i] + min(i, N - i) << endl;
  }
}

Submission Info

Judge Result