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
AC × 2
AC × 2
WA × 8
RE × 2
AC × 3
WA × 12
RE × 10
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