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 |
|
|
|
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 |