Submission #7996270
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <string> #include <set> #include <deque> #include <numeric> #include <bitset> #include <iomanip> using namespace std; typedef long long ll; typedef pair<int, int> P; int visit[100005]; int mod[100005]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, a; string s; cin >> n >> a >> s; --a; vector<int> b(n); for(int i = 0; i < n; ++i){ cin >> b[i]; --b[i]; } int now = a; ++visit[a]; vector<int> tmp; tmp.push_back(now); for(;;){ now = b[now]; if(visit[now] == 2) break; if(visit[now] == 0){ ++visit[now]; tmp.push_back(now); } else{ ++visit[now]; } } int st; // 閉路のスタート地点 for(int i = 0; i < (int)tmp.size(); ++i){ if(visit[tmp[i]] == 2){ st = i; break; } } int cnt = 0; // 閉路に含まれる頂点数 for(int i = 0; i < n; ++i){ if(visit[i] == 2){ ++cnt; } } int cnt2 = tmp.size() - cnt; // 閉路に含まれない頂点数 if(s < to_string(cnt2)){ int id = 0; int mul = 1; for(int i = (int)s.length() - 1; i >= 0; --i){ id += (s[i] - '0') * mul; mul *= 10; } cout << ++tmp[id] << endl; return 0; } mod[s.length()-1] = 1 % cnt; for(int i = (int)s.length() - 2; i >= 0; --i){ mod[i] = mod[i+1] * 10 % cnt; } // 操作回数の補正(この補正で閉路以外の頂点を辿ったことにする) int digit = to_string(cnt2).length(); if(s.substr((int)s.length() - digit, digit) >= to_string(cnt2)){ int num = 0; int mul = 1; for(int i = (int)s.length() - 1; i >= (int)s.length() - digit; --i){ int num2 = s[i] - '0'; num += num2 * mul; mul *= 10; } num -= cnt2; string t = to_string(num); for(int i = 0; i < digit; ++i){ if(i > t.length()){ s[s.length() - 1 - i] = '0'; } else{ s[s.length() - 1 - i] = t[t.length() - 1 - i]; } } } else{ int num = 0; int mul = 1; for(int i = (int)s.length() - 1; i >= (int)s.length() - digit - 1; --i){ int num2 = s[i] - '0'; num += num2 * mul; mul *= 10; } num -= cnt2; string t = to_string(num); for(int i = (int)s.length() - 1; i >= 0; --i){ if(i > t.length()){ s[s.length() - 1 - i] = '0'; } else{ s[s.length() - 1 - i] = t[t.length() - 1 - i]; } } } int sum = 0; for(int i = 0; i < (int)s.length(); ++i){ int num2 = s[i] - '0'; sum += mod[i] * num2 % cnt; } cout << ++tmp[st + sum] << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - へんてこ辞書 |
User | outline |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3199 Byte |
Status | RE |
Exec Time | 106 ms |
Memory | 1408 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 | RE | 105 ms | 896 KB |
subtask0_1.txt | WA | 7 ms | 768 KB |
subtask0_2.txt | RE | 104 ms | 896 KB |
subtask0_3.txt | WA | 6 ms | 768 KB |
subtask0_4.txt | WA | 9 ms | 896 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 | AC | 1 ms | 256 KB |
subtask0_sample_03.txt | AC | 1 ms | 256 KB |
subtask1_0.txt | RE | 103 ms | 896 KB |
subtask1_1.txt | RE | 104 ms | 1024 KB |
subtask1_10.txt | WA | 9 ms | 1232 KB |
subtask1_11.txt | WA | 1 ms | 256 KB |
subtask1_2.txt | RE | 103 ms | 1152 KB |
subtask1_3.txt | RE | 103 ms | 1024 KB |
subtask1_4.txt | WA | 7 ms | 1152 KB |
subtask1_5.txt | RE | 106 ms | 1280 KB |
subtask1_6.txt | RE | 103 ms | 1232 KB |
subtask1_7.txt | RE | 104 ms | 1152 KB |
subtask1_8.txt | RE | 106 ms | 1280 KB |
subtask1_9.txt | WA | 10 ms | 1408 KB |
subtask1_sample_02.txt | AC | 1 ms | 256 KB |