Envío 5208

Código

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <vector>
using namespace std;

using Permutation = std::unordered_map<int64_t, int64_t>;
using Cycle = std::vector<int64_t>;

void cyclePower(Cycle cycle, int64_t exponent, Permutation& outResult) {
  int64_t rotation = exponent % cycle.size();
  Permutation result;
  unordered_set<int64_t> seen;
  
  for (int32_t i = 0; i < cycle.size(); ++i) {
    int64_t currIdx = i;
    while (seen.count(currIdx) == 0) {
      seen.insert(currIdx);
      auto nextIdx = (currIdx + rotation) % cycle.size();
      outResult[cycle[nextIdx]] = cycle[currIdx];
      currIdx = nextIdx;
    }  
  }
}

int main() {
  int64_t N, R;

  cin >> N >> R;
  cin.ignore(1, '\n');

  std::vector<int64_t> input;
  for (int64_t i = 0; i < N; i++) {
    int num;
    cin >> num;
    input.push_back(num);
  }

  std::vector<Cycle> cycles;

  Cycle cycle;
  int32_t processed = 0;
  int64_t curr = 0;
  unordered_set<int64_t> seen;

  for(int start = 0; start < N; ++start) {
    if (seen.count(start) > 0) {
      continue;
    }

    cycle.push_back(start);
    seen.insert(start);
    auto curr = input[start];
    while (seen.count(curr) == 0) {
      cycle.push_back(curr);
      seen.insert(curr);
      curr = input[curr];      
    }
    cycles.push_back(std::move(cycle));
    cycle = {};
  }

  Permutation result;
  int i = 0;
  for (auto& cycle : cycles) {
    cyclePower(cycle, R, result);    
  }  

  for (int i = 0; i < N; ++i) {
    cout << result[i] + 1;
    if (i < N-1) {
      cout << " ";
    }
  }

  return 0;
}