Submission #1302884

---

Source Code Expand

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


#define REP(i, s, n) for(int i = s; i < n; ++i)
#define rep(i, n)		 REP(i, 0, n)
#define SORT(c)			 sort((c).begin(), (c).end())
#define IINF					INT_MAX
#define LLINF					LLONG_MAX
#define DEBUG					false
 
typedef long long				ll;
typedef pair <int, int> ii;

int main() {
	int n, a;
	ll k2 = LLINF;
	string k;
	cin >> n >> a >> k;
	vector<int> b(n+1);
	REP(i, 1, n + 1) cin >> b[i];
	if(k.size() < 9) k2 = stoi(k);
	vector<int> used;

	if(DEBUG) cout << n << endl << a << endl << k2 <<endl;

	if(DEBUG) REP(i, 1, n+1) cout << b[i] << endl;
	
	int word = a;
	int cycle;
	ll cnt = 0;
	vector<int>::iterator it;
	used.push_back(word);
	
	while(1){
		cnt++;
		word = b[word];
		if(DEBUG) cout << word << endl;
		if(cnt == k2){
			cout << word << endl;
			return 0;
		}
		it = find(used.begin(), used.end(), word);
		if(it != used.end()){
			cycle = used.size() - distance(used.begin(), it);
			break;
		}
		used.push_back(word);
	}
	if(DEBUG) cout << endl;
	
	if(DEBUG) rep(i, used.size()) cout << used[i] << endl;
	if(DEBUG) cout << endl;
	
	ll rem = 0;
	rep(i, k.size()){
		ll tmp = (ll)(k[i] - '0') + rem * 10;
		rem = tmp % cycle;
	}
	
	if(DEBUG) cout << rem << "\t" << cycle << "\t" << cnt << endl << endl;
	//cout << *it << endl << endl;
	//it = it + ((rem + cycle - cnt) % cycle);
	it = it + (((rem % cycle) + cycle * n - cnt) % cycle);
	cout << *it << endl;
	
	return 0;
}

Submission Info

Judge Result