Submission #137462

#	Time	Username	Problem	Language	Result	Execution time	Memory
137462		MladenP	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	883 ms	145504 KiB

scrivener

#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 1000010
#define MAXL 22
int trie[MAXN][27], anc[MAXN][MAXL], dub[MAXN];
vector<int> op;
int timer = 0;
void Init() {
    timer = 1;
    op.pb(1);
}

void TypeLetter(char L) {
    int c = L-'a'+1, cur = op.back();
    if(trie[cur][c] == 0) {
        trie[cur][c] = ++timer;
        anc[timer][0] = cur;
        dub[timer] = dub[cur] + 1;
        for(int i = 1; i < MAXL; i++) anc[timer][i] = anc[anc[timer][i-1]][i-1];
    }
    op.pb(trie[cur][c]);
}

void UndoCommands(int U) {
    op.pb(op[sz(op)-1-U]);
}

char GetLetter(int P) {
    int cur = op.back();
    P = dub[cur] - 1 - P;
    for(int k = MAXL-1; k >= 0; k--) {
        if((1<<k) <= P) {
            cur = anc[cur][k];
            P -= (1<<k);
        }
    }
    int par = anc[cur][0];
    for(int i = 1; i < 27; i++) {
        if(trie[par][i] == cur) return ('a'+i-1);
    }
}

Compilation message (stderr)

scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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