Submission #382386

#	Time	Username	Problem	Language	Result	Execution time	Memory
382386		Keshi	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	538 ms	136172 KiB

scrivener

//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 1e6 + 100;
const ll lg = 21;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll pos[maxn], g[maxn][26], t, c, h[maxn], p[maxn][lg];
char ch[maxn];

void Init(){
	
}
void TypeLetter(char L){
	ll x = ll(L - 'a');
	ll v = pos[c];
	if(!g[v][x]){
		g[v][x] = ++t;
		p[t][0] = v;
		h[t] = h[v] + 1;
		ch[t] = L;
		for(ll i = 1; i < lg; i++){
			p[t][i] = p[p[t][i - 1]][i - 1];
		}
	}
	pos[++c] = g[v][x];
	return;
}
void UndoCommands(int U){
	pos[c + 1] = pos[c - U];
	c++;
	return;
}
ll par(ll x, ll y){
	for(ll i = 0; i < lg; i++){
		if((y >> i) & 1) x = p[x][i];
	}
	return x;
}
char GetLetter(int P){
	ll x = h[pos[c]] - P - 1;
	return ch[par(pos[c], x)];
}


/*int main(){
    fast_io;
    
    Init();
	TypeLetter('a');
	TypeLetter('b');
	cout << GetLetter(1);
	TypeLetter('d');
	UndoCommands(2);
	UndoCommands(1);
	cout << GetLetter(2);
	TypeLetter('e');
	UndoCommands(1);
	UndoCommands(5);
	TypeLetter('c');
	cout << GetLetter(2);
	UndoCommands(2);
	cout << GetLetter(2);
 
    return 0;
}*/

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