Submission #270185

#	Time	Username	Problem	Language	Result	Execution time	Memory
270185		shayan_p	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	579 ms	167800 KiB

scrivener

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int h[maxn], sp[20][maxn];
int nxt[maxn][26];
int point[maxn];
int nw, C;

void Init(){
    memset(nxt, 0, sizeof nxt);
    nw = C = 0;
}
void TypeLetter(char c){
    if(nxt[point[nw]][c - 'a'] == 0){
	nxt[point[nw]][c - 'a'] = ++C;
	int pr = point[nw];
	h[C] = h[pr] + 1;
	sp[0][C] = pr;
	for(int i = 1; i < 20; i++)
	    sp[i][C] = sp[i-1][sp[i-1][C]];
    }
    nw++;
    point[nw] = nxt[point[nw-1]][c - 'a'];
}
void UndoCommands(int U){
    nw++;
    point[nw] = point[nw - 1 - U];
}
char GetLetter(int p){
    int u = point[nw];
    ++p;
    p = h[u] - p;
    for(int i = 0; i < 20; i++)
	if(bit(p, i))
	    u = sp[i][u];
    for(int i = 0; i < 26; i++){
	if(nxt[ sp[0][u] ][i] == u){
	    return 'a' + i;
	}
    }
    assert(0);
}

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