Submission #7997170
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; // 閉路のスタート地点のtmpのindex 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 = (int)tmp.size() - cnt; // 閉路に含まれない頂点数 int len = (int)s.length(); int digit1 = (int)(to_string(cnt).length()); int digit2 = (int)(to_string(cnt2).length()); if(len <= digit2){ int num = 0; int mul = 1; for(int i = len - 1; i >= 0; --i){ num += (s[i] - '0') * mul; mul *= 10; } if(num < cnt2){ // 閉路に入っていない場合 cout << ++tmp[num] << endl; return 0; } num -= cnt2; string t = to_string(num); for(int i = 0; i < len; ++i){ if(i >= len) break; if(i >= (int)t.length()){ s[len - 1 - i] = '0'; } else{ s[len - 1 - i] = t[len - 1 - i]; } } for(int i = 0; i < len; ++i){ mod[i+1] = (mod[i] * 10 % cnt + (s[i] - '0')) % cnt; } cout << ++tmp[st + mod[len]] << endl; return 0; } int num = 0; int mul = 1; for(int i = len - 1; i >= len - digit2; --i){ num += (s[i] - '0') * mul; mul *= 10; } // 操作回数の補正(この補正で閉路以外の頂点を辿ったことにする) if(num >= cnt2){ num -= cnt2; string t = to_string(num); int len2 = (int)t.length(); for(int i = 0; i < digit2; ++i){ if(i >= len) break; if(i >= len2){ s[len - 1 - i] = '0'; } else{ s[len - 1 - i] = t[len2 - 1 - i]; } } } else{ num += (s[len - digit2 - 1] - '0') * mul; num -= cnt2; string t = to_string(num); int len2 = (int)t.length(); for(int i = 0; i < digit2 + 1; ++i){ if(i >= len) break; if(i >= len2){ s[len - 1 - i] = '0'; } else{ s[len - 1 - i] = t[len2 - 1 - i]; } } } for(int i = 0; i < len; ++i){ mod[i+1] = (mod[i] * 10 % cnt + (s[i] - '0')) % cnt; } cout << ++tmp[st + mod[len]] << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - へんてこ辞書 |
User | outline |
Language | C++14 (GCC 5.4.1) |
Score | 50 |
Code Size | 3513 Byte |
Status | WA |
Exec Time | 11 ms |
Memory | 1616 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 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 | AC | 8 ms | 1024 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 | 9 ms | 896 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 | 8 ms | 1152 KB |
subtask1_1.txt | AC | 9 ms | 1408 KB |
subtask1_10.txt | WA | 11 ms | 1616 KB |
subtask1_11.txt | WA | 1 ms | 256 KB |
subtask1_2.txt | AC | 7 ms | 1152 KB |
subtask1_3.txt | AC | 6 ms | 1024 KB |
subtask1_4.txt | AC | 7 ms | 1152 KB |
subtask1_5.txt | AC | 9 ms | 1280 KB |
subtask1_6.txt | AC | 8 ms | 1232 KB |
subtask1_7.txt | AC | 7 ms | 1152 KB |
subtask1_8.txt | AC | 10 ms | 1280 KB |
subtask1_9.txt | AC | 10 ms | 1408 KB |
subtask1_sample_02.txt | AC | 1 ms | 256 KB |