AtCoder Beginner Contest 030

Submission #1357013

Source codeソースコード

#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) << endl;
    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

Task問題 D - へんてこ辞書
User nameユーザ名 rpy3cpp
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1398 Byte
File nameファイル名
Exec time実行時間 10 ms
Memory usageメモリ使用量 1232 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_03.txt
Subtask1 50 / 50 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 50 / 50 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_0.txt AC 8 ms 896 KB
subtask0_1.txt AC 7 ms 768 KB
subtask0_2.txt AC 8 ms 896 KB
subtask0_3.txt AC 6 ms 768 KB
subtask0_4.txt AC 8 ms 1024 KB
subtask0_5.txt AC 7 ms 768 KB
subtask0_6.txt AC 6 ms 768 KB
subtask0_7.txt AC 8 ms 896 KB
subtask0_8.txt AC 6 ms 768 KB
subtask0_9.txt AC 8 ms 896 KB
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_03.txt AC 1 ms 256 KB
subtask1_0.txt AC 7 ms 896 KB
subtask1_1.txt AC 8 ms 1024 KB
subtask1_10.txt AC 10 ms 1232 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_2.txt AC 7 ms 896 KB
subtask1_3.txt AC 6 ms 768 KB
subtask1_4.txt AC 7 ms 896 KB
subtask1_5.txt AC 10 ms 1024 KB
subtask1_6.txt AC 7 ms 848 KB
subtask1_7.txt AC 6 ms 768 KB
subtask1_8.txt AC 9 ms 1152 KB
subtask1_9.txt AC 9 ms 1152 KB
subtask1_sample_02.txt AC 1 ms 256 KB