Envío 5205

Código

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

using Permutation = unordered_map<int64_t, int64_t>;

// Order matters, apply first p2 then p1
Permutation composition(const Permutation& p1, const Permutation& p2) {
  unordered_set<int64_t> keys;
  for (auto& pair: p1) {
    keys.insert(pair.first);
  }
  for (auto& pair: p2) {
    keys.insert(pair.first);
  }

  Permutation result;
  for (auto key: keys) {
    int64_t next = key;
    auto nextPtr = p2.find(next);
    if (nextPtr != p2.end()) {
      next = nextPtr->second;
    }

    nextPtr = p1.find(next);
    if (nextPtr != p1.end()) {
      next = nextPtr->second;
    }

    result[key] = next;
  }

  return result;
}

Permutation power(Permutation permutation, int64_t exponent) {
  if (exponent == 0) {
    return {};
  }
  if (exponent == 1) {
    return permutation;
  }    

  auto tempPerm = power(permutation, exponent / 2);
  if (exponent % 2 == 0) {
    return composition(tempPerm, tempPerm);
  } else {
    auto tempPerm2 = composition(tempPerm, tempPerm);
    return composition(tempPerm2, permutation);
  }
}

int main() {
  int64_t N, R;

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

  Permutation permutation;
  for(int64_t i = 0; i < N; i++) {
    int num;
    cin >> num;
    permutation[i] = num;
  }

  Permutation result = power(permutation, R);
  std::vector<int64_t> final(N, -1);
  for(int64_t i = 0; i < N; i++) {
    auto res = i;

    auto nextPtr = result.find(i);
    if (nextPtr != result.end()) {
      res = nextPtr->second;
    }
    final[res] = i + 1;    
  }

  for(int64_t i = 0; i < final.size(); i++) {
    cout << final[i];
    if (i != final.size() - 1) {
      cout << " ";
    }
  }

  return 0;
}