Submission #321614

#	Time	Username	Problem	Language	Result	Execution time	Memory
321614		nikatamliani	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1051 ms	71900 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, A = 26;
int nodes = 0, pos;
int code[N][A], depth[N];
pair<int, char> par[N];
vector<int> v;
void TypeLetter(char c) {
    if(!code[pos][c - 'a']) {
        code[pos][c - 'a'] = ++nodes;
        par[nodes] = {pos, c};
        depth[nodes] = depth[pos] + 1; 
    }
    v.push_back(code[pos][c - 'a']); 
    pos = v.back(); 
}
void UndoCommands(int x) {
    assert((int)v.size() - 1 - x >= 0);
    pos = v[(int)v.size() - 1 - x];
    v.push_back(pos);
}
char GetLetter(int index) {
    int size = depth[pos];
    int up = size - index - 1;
    int answer = pos; 
    while(depth[answer] != index + 1) {
        answer = par[answer].first;
    }
    return par[answer].second;
}
void Init() {
    
}
// int main() {
//     int k;
//     cin >> k;
//     while(k--) {
//         int type;
//         cin >> type;
//         if(type == 1) {
//             char c;
//             cin >> c;
//             TypeLetter(c);
//         } else if(type == 2) {
//             int x;
//             cin >> x;
//             UndoCommands(x);
//         } else {
//             int x;
//             cin >> x;
//             cout << GetLetter(x) << ' ';
//         }
//     }
// }

Compilation message (stderr)

scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:24:9: warning: unused variable 'up' [-Wunused-variable]
   24 |     int up = size - index - 1;
      |         ^~

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