Expert.
Put your skills to the test.

Problem summary

Cards initially labeled 1 through N are in that order. In one simultaneous operation the card at position i moves to position pi. Print the arrangement after M operations.

Constraints

1 < N < 30000; 0 < M < 10^17; p is a permutation of 1,…,N.

Worked example

Official example, transcribed with whitespace restored from the PDF.

5 2
3 1 5 4 2

5 3 2 4 1

Solution analysis

1. Decompose the position permutation into disjoint directed cycles. A card cannot leave its cycle, and one operation advances it by exactly one place around that cycle.
2. For a cycle c of length L, M operations advance each original card by M mod L. Assign answer[c[(j+M mod L) mod L]]=c[j]+1 for every index j, using zero-based internal positions.
3. In the sample, positions 1→3→5→2→1 form a four-cycle while position 4 is fixed. Rotating the four-cycle by two produces the printed arrangement.

Why it works

Disjoint cycles partition all positions. Repeated composition of a cycle advances an element by the number of compositions modulo its length. The assignment puts every original card at exactly this destination; destinations are distinct within and between cycles, so the entire resulting arrangement is correct.

Watch out. The input maps source positions to destinations; writing the powered permutation directly would print the inverse arrangement.

An independently written complete program with standard headers.

// Key idea: Disjoint cycles partition all positions. Repeated composition of a cycle advances an
// element by the number of compositions modulo its length.
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin>>n>>m;
    vector<int>p(n),answer(n),seen(n);
    for(int&x:p){
        cin>>x;
        --x;
    }
    for(int start=0;start<n;++start){
        if(seen[start]){
            continue;
        }
        vector<int>cycle;
        int v=start;
        do{
            seen[v]=1;
            cycle.push_back(v);
            v=p[v];
        }
        while(v!=start);
        int length=static_cast<int>(cycle.size());
        int shift=static_cast<int>(m%length);
        for(int j=0;j<length;++j){
            answer[cycle[(j+shift)%length]]=cycle[j]+1;
        }
    }
    for(int i=0;i<n;++i){
        cout<<(i?" ":"")<<answer[i];
    }
    cout<<'\n';
}