Submission #447869

#	Time	Username	Problem	Language	Result	Execution time	Memory
447869		Pietra	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	450 ms	75580 KiB

scrivener

#include<bits/stdc++.h>
using namespace std ; 

const int maxn = 1e6 + 5 ; 
const int maxl = 23 ; 

int n, tempo, t[maxn], h[maxn], tab[maxl][maxn] ; 
char s[maxn] ; 

void TypeLetter(char L) {
   
   n++ ; tempo++ ; 

   t[tempo] = n ; 
   s[n] = L ; 

   tab[0][n] = t[tempo-1] ; 
   h[n] = h[t[tempo-1]] + 1 ; 

   for(int i = 1 ; i < maxl ; i++) tab[i][n] = tab[i-1][tab[i-1][n]] ; 

}
 
void UndoCommands(int U) {

	tempo++ ; 
	t[tempo] = t[tempo - U - 1] ; 

}
 
char GetLetter(int P) {

	int at = t[tempo] ; 
	int alt = h[t[tempo]] - P - 1 ; 

	for(int i = maxl - 1 ; i >= 0 ; i--){
		if(alt >= (1<<i)) alt -= (1<<i), at = tab[i][at] ; 
	}

	return s[at] ; 

}

void Init(){

}

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