AtCoder Beginner Contest 030

Submission #1357009

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);
    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状態 WA
Score得点 0
Source lengthソースコード長 1390 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_03.txt
Subtask1 0 / 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 0 / 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 WA
subtask0_1.txt WA
subtask0_2.txt WA
subtask0_3.txt WA
subtask0_4.txt WA
subtask0_5.txt WA
subtask0_6.txt WA
subtask0_7.txt WA
subtask0_8.txt WA
subtask0_9.txt WA
subtask0_sample_01.txt WA
subtask0_sample_03.txt WA
subtask1_0.txt WA
subtask1_1.txt WA
subtask1_10.txt WA
subtask1_11.txt WA
subtask1_2.txt WA
subtask1_3.txt WA
subtask1_4.txt WA
subtask1_5.txt WA
subtask1_6.txt WA
subtask1_7.txt WA
subtask1_8.txt WA
subtask1_9.txt WA
subtask1_sample_02.txt WA