Submission #321616

#	Time	Username	Problem	Language	Result	Execution time	Memory
321616		nikatamliani	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	579 ms	154644 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, A = 26;
int nodes = 0, pos;
int code[N][A], par[N][A], depth[N];
char ch[N];
vector<int> v;
void TypeLetter(char c) {
    if(!code[pos][c - 'a']) {
        code[pos][c - 'a'] = ++nodes;
        ch[nodes] = c;
        par[nodes][0] = pos;
        for(int x = 1; x < A; ++x) {
            par[nodes][x] = par[par[nodes][x - 1]][x - 1];
        }
        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 answer = pos; 
    int up = depth[answer] - (index + 1);
    for(int i = 0; i < A; ++i) {
        if(up >> i & 1) {
            answer = par[answer][i];
        }
    }
    return ch[answer];
}
void Init() {
    
}

Compilation message (stderr)

scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:27:9: warning: unused variable 'size' [-Wunused-variable]
   27 |     int size = depth[pos];
      |         ^~~~

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