Submission #1161006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161006		SmuggingSpun	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++20	100 / 100	768 ms	166628 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
const int lim = 1e6 + 5;
pair<int, int>up[lim][21];
vector<char>S;
void Init(){
    for(int i = 0; i < lim; i++){
        for(int j = 0; j < 21; j++){
            up[i][j] = make_pair(0, 0);
        }
    }
    S.emplace_back('#');
}
void add_edge(int u, int v, bool w){
    up[u][0] = make_pair(v, int(w));
    for(int i = 1; i < 21; i++){
        up[u][i].first = up[up[u][i - 1].first][i - 1].first;
        up[u][i].second = up[u][i - 1].second + up[up[u][i - 1].first][i - 1].second;
    }
}
void TypeLetter(char L){
    add_edge(S.size(), int(S.size()) - 1, true);
    S.emplace_back(L);
}
void UndoCommands(int U){
    add_edge(S.size(), int(S.size()) - U - 1, false);
    S.emplace_back('#');
}
char GetLetter(int P){
    int index = int(S.size()) - 1;
    P = up[index][20].second - P - 1;
    for(int i = 20; i > -1; i--){
        if(up[index][i].second <= P){
            P -= up[index][i].second;
            index = up[index][i].first;
        }
    }
    return S[index];
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40