Submission #253286

#	Time	Username	Problem	Language	Result	Execution time	Memory
253286		ivandasfs	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	913 ms	173344 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

vector <int> pos;

int f = 1;

int trei[1000005][26];
int par[1000005][22];
int d[1000005];

void Init() {
	//memset(par, -1, sizeof par);
	d[0] = 0;
	memset(trei, -1, sizeof trei);
	pos.pb(0);
}

void TypeLetter(char c) {
	int p = pos.back();
	int x = c - 'a';
//	cout <<p<<", "<<d[p]<<endl;
	if (trei[p][x] != -1) {
	//	cout <<"a\n";
		pos.pb(trei[p][x]);
	} else {
	//	cout <<"b\n";
		pos.pb(f);
		trei[p][x] = f;
		par[f][0] = p;
		for (int i=1 ; i<22 ; i++) {
			par[f][i] = par[par[f][i-1]][i-1];
		}
		d[f] = d[p]+1;
		f++;
	}
}

void UndoCommands(int u) {
	pos.pb(pos[pos.size()-u-1]);
}

char GetLetter(int k) {
	int p = pos.back();
//	cout <<p<<", "<<d[p]<<endl;
	for (int i=21 ; i>=0 ; i--) {
		if (d[par[p][i]] > k) {
			p = par[p][i];
		}
	}
//	cout <<"p = "<<p<<endl;
	for (int x=0 ; x<26 ; x++) {
		if (trei[par[p][0]][x] == p) {
			return 'a' + x;
		}
	}
}
/*
int main() {
	while (1) {
		char c;
		cin >>c;
		if (c == 'I') Init();
		if (c == 'T') {
			char x;
			cin >>x;
			TypeLetter(x);
		}
		if (c == 'G') {
			int x;
			cin >>x;
			cout <<GetLetter(x)<<endl;
		}
		if (c == 'U') {
			int x;
			cin >>x;
			UndoCommands(x);
		}
	}
	return 0;
}*/

Compilation message (stderr)

scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:68: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