Submission #1357009


Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <tuple>

using namespace std;

int solve(string k, int a, const vector<int> &bs);

pair<int, int> find_cycle(int a, const vector<int> &bs){
    vector<int> order(bs.size(), -1);
    int i = 0;
    while (order[a - 1] == -1){
        order[a - 1] = i++;
        a = bs[a - 1];
    }
    int head = order[a - 1];
    int cycle = i - head;
    return make_pair(head, cycle);
}

int solve_large(string k, int a, const vector<int> &bs){
    int head, cycle;
    tie(head, cycle) = find_cycle(a, bs);
    int kk = 0;
    for (char c : k) kk = (kk * 10 + c - '0') % cycle;
    if (kk < head) kk += (head / cycle + 1) * cycle;
    while (kk--) a = bs[a - 1];
    return a;
}

int solve_small(string k, int a, const vector<int> &bs){
    int kk = 0;
    for (char c : k) kk = kk * 10 + c - '0';
    while (kk--) a = bs[a - 1];
    return a;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, a;
    cin >> N >> a;
    string k;
    cin >> k;
    vector<int> bs(N);
    for (auto & b : bs) cin >> b;
    cout << solve(k, a, bs);
    return 0;
}

int solve(string k, int a, const vector<int> &bs){
    if (k.size() <= 5 or k == "100000"){
        return solve_small(k, a, bs);
    }else{
        return solve_large(k, a, bs);
    }
}

Submission Info

Submission Time
Task D - へんてこ辞書
User rpy3cpp
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1390 Byte
Status WA
Exec Time 10 ms
Memory 1232 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 50 0 / 50
Status
WA × 2
WA × 12
WA × 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 WA 8 ms 896 KB
subtask0_1.txt WA 7 ms 768 KB
subtask0_2.txt WA 8 ms 896 KB
subtask0_3.txt WA 6 ms 768 KB
subtask0_4.txt WA 8 ms 1024 KB
subtask0_5.txt WA 7 ms 768 KB
subtask0_6.txt WA 6 ms 768 KB
subtask0_7.txt WA 8 ms 896 KB
subtask0_8.txt WA 6 ms 768 KB
subtask0_9.txt WA 8 ms 896 KB
subtask0_sample_01.txt WA 1 ms 256 KB
subtask0_sample_03.txt WA 1 ms 256 KB
subtask1_0.txt WA 7 ms 896 KB
subtask1_1.txt WA 8 ms 1024 KB
subtask1_10.txt WA 10 ms 1232 KB
subtask1_11.txt WA 1 ms 256 KB
subtask1_2.txt WA 7 ms 896 KB
subtask1_3.txt WA 6 ms 768 KB
subtask1_4.txt WA 7 ms 896 KB
subtask1_5.txt WA 8 ms 1024 KB
subtask1_6.txt WA 7 ms 848 KB
subtask1_7.txt WA 6 ms 768 KB
subtask1_8.txt WA 9 ms 1152 KB
subtask1_9.txt WA 9 ms 1152 KB
subtask1_sample_02.txt WA 1 ms 256 KB