Submission #8191541


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define p2(s, t) cout << (s) << " " << (t) << '\n'
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << '\n'

const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll bigMod(string s, ll mod){
    int tmp=0;
    FOR(i, 0, s.size()){
        tmp = (tmp*10+s[i]-'0') % mod;
    }
    return tmp;
}

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

    // input
    ll N, a;
    cin >> N >> a;
    a--;

    // でかい
    string k; cin >> k;

    ll K;
    if(k.size()>6){
      K = inf;
    }else{
      K = stoll(k);
    }

    VI B(N);
    rep(i, N){
      cin >> B.at(i);
      B[i]--;
    }

    if(K==inf){
      VI T(N, -1); // visited time
      ll t = 0;
      T[a] = t;
      t++;
      ll loop;
      while(1){
        a = B[a];
        if(T[a]!=-1){
          loop = t - T[a];

          ll loop_start_t = T[a];
          ll temp = bigMod(k, loop);  
          ll rest = temp - loop_start_t%loop;
          if(rest<0){
            rest+=loop;
          }
          K = rest;
          break;
        }
        T[a] = t;
        t++;
      }
    }

    // 単純にシミュレート
    while(K--){
      a = B[a];
    }
    p(a+1);
    
    return 0;
}

Submission Info

Submission Time
Task D - へんてこ辞書
User peroon
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1638 Byte
Status
Exec Time 10 ms
Memory 1920 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
× 2
× 12
× 25
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_03.txt
Subtask1 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_03.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_03.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt, subtask1_sample_02.txt
Case Name Status Exec Time Memory
subtask0_0.txt 8 ms 1664 KB
subtask0_1.txt 7 ms 1408 KB
subtask0_2.txt 8 ms 1536 KB
subtask0_3.txt 6 ms 1152 KB
subtask0_4.txt 9 ms 1664 KB
subtask0_5.txt 7 ms 1408 KB
subtask0_6.txt 6 ms 1152 KB
subtask0_7.txt 8 ms 1536 KB
subtask0_8.txt 6 ms 1152 KB
subtask0_9.txt 8 ms 1664 KB
subtask0_sample_01.txt 1 ms 256 KB
subtask0_sample_03.txt 1 ms 256 KB
subtask1_0.txt 8 ms 1408 KB
subtask1_1.txt 9 ms 1664 KB
subtask1_10.txt 10 ms 1872 KB
subtask1_11.txt 1 ms 256 KB
subtask1_2.txt 7 ms 1408 KB
subtask1_3.txt 6 ms 1152 KB
subtask1_4.txt 7 ms 1280 KB
subtask1_5.txt 9 ms 1664 KB
subtask1_6.txt 7 ms 1360 KB
subtask1_7.txt 7 ms 1280 KB
subtask1_8.txt 10 ms 1920 KB
subtask1_9.txt 10 ms 1920 KB
subtask1_sample_02.txt 1 ms 256 KB