Submission #73300439

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 500010;

int A[MAXN];
int ans[MAXN];
int vis[MAXN];

void solve(int start, int N) {
    vector<int> path;
    int u = start;
    
    while (vis[u] == 0) {
        vis[u] = 1;
        path.push_back(u);
        u = A[u];
        if (u < 1 || u > N) break;
    }
    
    int final_pos;
    if (vis[u] == 2) {
        final_pos = ans[u];
    } else {
        int cycle_start_idx = 0;
        while (cycle_start_idx < (int)path.size() && path[cycle_start_idx] != u) {
            cycle_start_idx++;
        }
        final_pos = u;
        for (int i = cycle_start_idx; i < (int)path.size(); ++i) {
            ans[path[i]] = final_pos;
            vis[path[i]] = 2;
        }
    }
    
    for (int i = 0; i < (int)path.size(); ++i) {
        if (vis[path[i]] == 2) break;
        ans[path[i]] = final_pos;
        vis[path[i]] = 2;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        if (A[i] < 1 || A[i] > N) {
            A[i] = i;
        }
    }
    
    memset(ans, 0, sizeof(ans));
    memset(vis, 0, sizeof(vis));
    
    for (int s = 1; s <= N; ++s) {
        if (vis[s] == 0) {
            solve(s, N);
        }
    }
    
    for (int s = 1; s <= N; ++s) {
        if (s > 1) cout << " ";
        cout << ans[s];
    }
    cout << "\n";
    
    return 0;
}

Submission Info

Judge Result