Submission #13081304

---

Source Code Expand

#include <bits/stdc++.h>

// definitions
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define rep(i, l, r) for (long long i = (l); i < (long long)(r); i++)
#define repb(i, r, l) for (long long i = (r); i > (long long)(l); i--)
#define pb push_back
#define pf push_front
#define mod1 998244353
#define mod 1000000007
#define MAX_CHAR 256


using namespace std;
typedef vector<long long> vl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector< pair<long long, long long> > vp;
typedef vector<tuple<long long , long long , long long> > vtup;
typedef deque <long long> dql;
typedef deque <char> dqc;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;


// prevent collisions in unordered_map
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef unordered_map <long long, long long, custom_hash> umap;


// standard functions
ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
} 

ll mystoi(string str)
{
    stringstream ss(str);
    ll ans=0;
    ss >> ans;

    return ans;
}


ll exp(ll x, ll ex) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x);
        ex >>= 1ll;
        x = (x * x);
    }
    return ans;
} 
 
ll nCrModp(ll n, ll r, ll p) 
{ 
    ll C[r+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1; 
    for (ll i = 1; i <= n; i++) 
    { 
        for (ll j = min(i, r); j > 0; j--) 
            C[j] = (C[j] + C[j-1])%p; 
    } 
    return C[r]; 
}
 
bool isPrime(ll n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true;  
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 
 
vl countFreq(ll arr[], ll n) 
{ 
    unordered_map<ll, ll> mp; 
    vector <ll> v;
    
    for (ll i = 0; i < n; i++) 
        mp[arr[i]]++; 
   
    for (auto x : mp) 
        v.pb(x.second);
    
    return v;
}

ll binarySearch(ll arr[], ll l, ll r, ll x) 
{ 
    while (l <= r) 
    { 
        ll m = l + (r - l) / 2; 
        if (arr[m] == x) 
            return m; 
        if (arr[m] < x) 
            l = m + 1; 
        else
            r = m - 1; 
    }
    return -1; 
}

bool sort_cond(const pair<ll,ll> &a, const pair <ll,ll> &b)
{
    return a.second > b.second;
}

const ll MAXSIEVE=(1e3);
ll spf[MAXSIEVE];
void sieve() 
{ 
    spf[1] = 1; 
    for (ll i=2; i<MAXSIEVE; i++) 
        spf[i] = i; 

    for (ll i=4; i<MAXSIEVE; i+=2) 
        spf[i] = 2; 
  
    for (ll i=3; i*i<MAXSIEVE; i++) 
    { 
        if (spf[i] == i) 
        { 
            for (ll j=i*i; j<MAXSIEVE; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
}

bool findPair(int arr[], int size, int n)  
{
    int i = 0;  
    int j = 1;  
  
    while (i < size && j < size)  
    {  
        if(j-i>1 && arr[j]-arr[i]==n)
        return true;

        else if(arr[j]-arr[i]<=n)
            j++;
        else
            i++;

    }  
    return false;  
}



// code beigns in main
int main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll t=1;
    // cin >> t;
    
    while(t--)
    {
        ll n,k;
        cin >> n >>k;

        ll arr[n];
        ll count[(ll)4e5]={0};
        rep(i,0,n)
        {
            cin >> arr[i];
        }


        if(k<=n)
        {
            ll t=1;
            rep(i,0,k)
            {
                t=arr[t-1];
            }
            cout << t << endl;
            return 0;
        }


        vl seq;
        ll tar;
        ll t=1;
        while(true)
        {
            if(count[t]==1)
            {
                tar=t;
                break;
            }
            else
            {
                count[t]++;
                seq.pb(t);
                t=arr[t-1];
            }
        }

        vl ans;
        ll sub=0;
        bool ok=1;
        rep(i,0,seq.size())
        {
            if(seq[i]!=tar && ok)
                sub++;
            else
            {
                ok=0;
                ans.pb(seq[i]);
            }
        }

        // cout << sub << endl;
        // rep(i,0,ans.size())
        // cout << ans[i] <<" ";

        // cout << endl;

        ll v=k-sub;
        v%=ans.size();
        cout << ans[v] << endl;
    }
}

Submission Info

Judge Result