Envío 5207

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) {
    Cycle result;
    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;
    }  
  }
}

void printPerm(Cycle cycle) {
  for (auto elem : cycle) {
    cout << elem << " ";
  }
  cout << endl;
}

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;
  while (processed < N) {
    cycle.push_back(curr);
    seen.insert(curr);
    curr = input[curr];

    if (seen.count(curr) > 0) {
      seen.clear();
      cycles.push_back(std::move(cycle));
      cycle = {};
      curr = processed + 1;
    }
    processed += 1;
  }

  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;
}