HackerRank Number Theory – Long Permutation

Challenge: Long Permutation

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464754841

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/long-permutation/problem

Cerinta

Consider an inifite array, $a$, of positive numbers, $a_1, a_2, \dots$, where each $a_i = i$. You can apply a permutation, $p$, of size $n$ (i.e., $n$ different numbers $1 \le p_1, \ldots, p_{n} \le n$) to the $n$-element subset of your array from $a_1$ through $a_{n}$ in the following way:  

$$ (a_1, \dots, a_{n}) \rightarrow (a_{p_{1}}, \dots, a_{p_{n}}).$$ 
   
To get infinite array $b$, you must apply permutation $p$ to the first $n$ elements ($a_1$ to $a_{n}$), then to elements $a_2$ through $a_{n+1}$, then to elements $a_3$ through $a_{n+2}$, and so on, infinitely many times. 

Given the values of $n$, $m$, and $p$, find and print the value of $b_m$. See the *Explanation* section below for more detail. 

**Note:** This challenge uses $1$-based array indexing.

Input Format

The first line contains $2$ space-separated integers, $n$ and $m$, respectively.  
The second line contains $n$ space-separated integers describing the respective values of $p_1, p_2, \dots, p_{n}$.

Output Format

Print a single integer denoting the value of $b_m$.

**Sample Input 0**

    2 10
    2 1
    
**Sample Output 0**

	11

**Sample Input 1**

	3 1
	2 3 1
    
**Sample Output 1**

	2
    
**Sample Input 2**

	3 10
    2 3 1
    
**Sample Output 2**

	10

Constraints

- $1 \le n \le 10^5$
- $1 \le m \le 10^{18}$  
- $1 \le p_1, p_2, \dots, p_{n} \le n$, and each $p_i$ is unique.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long m;
    if (!(cin >> n >> m)) return 0;

    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) cin >> p[i];

    int s = p[1];

    if (s == n) {
        cout << (m + (long long)n - 1) << '\n';
        return 0;
    }

    // g(i) = p[i+1] for i in [1..n-1]
    vector<int> g(n + 1, 0);
    for (int i = 1; i <= n - 1; ++i) g[i] = p[i + 1];

    vector<int> path;
    path.reserve(n);
    int x = s;
    path.push_back(x);
    while (x != n) {
        x = g[x];
        path.push_back(x);
    }

    long long r = (long long)path.size() - 1; // distance from s to n in the g-graph

    if (m <= (long long)path.size()) {
        cout << path[(size_t)m - 1] << '\n';
    } else {
        cout << (m + (long long)n - 1 - r) << '\n';
    }

    return 0;
}