Submission #908466

#	Time	Username	Problem	Language	Result	Execution time	Memory
908466		Blagoj	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	739 ms	90976 KiB

scrivener

#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

const int mxn = 1e6 + 10;

int nxt[mxn][21], sz[mxn], cnt = 0;
char c[mxn];

void Init() { }

void TypeLetter(char L) { 
	cnt++;
	c[cnt] = L;
	sz[cnt] = sz[cnt - 1] + 1;
	nxt[cnt][0] = cnt - 1;
	for (int i = 1; i <= 20; i++) nxt[cnt][i] = nxt[nxt[cnt][i - 1]][i - 1];
}

void UndoCommands(int U) {
	cnt++;
	sz[cnt] = sz[cnt - U - 1];
	nxt[cnt][0] = nxt[cnt - U - 1][0];
	c[cnt] = c[cnt - U - 1];
	for (int i = 1; i <= 20; i++) nxt[cnt][i] = nxt[nxt[cnt][i - 1]][i - 1];
}

char GetLetter(int P) { 
	int len = sz[cnt] - P - 1;
	int ans = cnt;
	for (int i = 20; i >= 0; i--) {
		if (len & (1 << i)) ans = nxt[ans][i];
	} 
	return c[ans];
}

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