Envío 5206

Código

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

using Permutation = std::vector<int64_t>;

// Cycle power might give multiple cycles back
std::vector<Permutation> cyclePower(Permutation cycle, int64_t exponent) {
  int64_t rotation = exponent % cycle.size();
  std::vector<Permutation> results;
  unordered_set<int64_t> seen;
  
  for (int32_t i = 0; i < cycle.size(); ++i) {
    Permutation result;
    int64_t currIdx = i;
    while (seen.count(currIdx) == 0) {
      seen.insert(currIdx);
      result.push_back(cycle[currIdx]);
      currIdx = (currIdx + rotation) % cycle.size();
    }
    if (!result.empty()) {
      results.push_back(std::move(result));
    }    
  }
  return results;
}

void printPerm(Permutation 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<Permutation> cycles;

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

  std::vector<int64_t> result;
  int i = 0;
  for (auto& cycle : cycles) {
    auto tmpCycles = cyclePower(cycle, R);
    for (auto tmpCycle : tmpCycles) {
      std::map<int64_t, int64_t> invMapping;
      for (int i = 0; i < tmpCycle.size(); ++i) {
        invMapping[tmpCycle[(i+1) % tmpCycle.size()]] = tmpCycle[i];
      }
      for (auto pair: invMapping) {
        cout << pair.second + 1;        
        if (i < N-1) {
          cout << " ";
        }
        i += 1;
      }
    }
  }  

  return 0;
}