Submission #234549

#	Time	Username	Problem	Language	Result	Execution time	Memory
234549		crossing0ver	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	894 ms	86648 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;        
int operations;
char lastchar[1000005];
int P[1000005][20],sz[1000005];
void Init() {}    

void TypeLetter(char L){
	operations++;
	P[operations][0] = operations - 1;
	sz[operations] = sz[operations - 1] + 1;
	for (int i = 1; i < 20; i ++)
		P[operations][i] = P[ P[operations][i-1] ][i-1];
	lastchar[operations] = L;
}

void UndoCommands(int U) {
	operations++;
	sz[operations] = sz[operations - 1 - U];
	P[operations][0] = P[operations - 1 - U][0];
	lastchar[operations]= lastchar[operations - 1 - U];
	for (int i = 1; i < 20; i++)
		P[operations][i] = P[ P[operations][i-1] ][i-1];
}


char GetLetter(int p) {
	int x = sz[operations] - p - 1;
	int cur = operations;
	for (int i = 0; i < 20 ;i++) {
		if (x & (1 << i)) {
			cur = P[cur][i];
		}
	}
	return lastchar[cur];
}

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