Submission #260453

#	Time	Username	Problem	Language	Result	Execution time	Memory
260453		youssefbou62	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	527 ms	67288 KiB

scrivener

#include <bits/stdc++.h>

#define pb push_back 
#define sz(x)	(int)x.size()
#define fi first 
#define se second 
using namespace std ; 

const int MAXN = 1e6+6 ;

char val[MAXN]; 
int cnt,t,node,pos[MAXN],len[MAXN],par[MAXN][20]; 

void Init() {

}

void new_state(int s){
	for(int i=1;i<19;i++){
		par[s][i] = par[par[s][i-1]][i-1]; 
	}

}

int kth_anc(int u,int k){
	for(int i = 18 ; i >= 0 ; i-- ){
		if(k&(1<<i)){
			k-=(1<<i); 
			u = par[u][i] ; 
		}
	}
	return u; 
}


void TypeLetter(char L) {
	t ++ ; 
	pos[t] = cnt ; 
	par[cnt][0] = node; 
	len[cnt] = len[node] + 1 ; 
	node = cnt; 
	val[cnt] = L ; 
	new_state(node); 
	cnt ++ ; 

		
}

void UndoCommands(int U) {
	node = pos[t-U];
	t++ ; 
	pos[t] = node ; 
}


char GetLetter(int P) {
	int L = len[node] ; 
	// cerr << len[node] << endl; 
	return val[kth_anc(pos[t],L-P-1)]; 

}


// int main() {
//   Init();

//   int cmd_num;
//   bool tmp = scanf("%d", &cmd_num);
//   assert(tmp == 1);

//   int i;
//   for (i = 0; i < cmd_num; i++) {
//     char cmd;
//     tmp = scanf(" %c", &cmd);
//     assert(tmp == 1);
//     if (cmd == 'T') {
//       char letter;
//       tmp = scanf(" %c", &letter);
//       assert(tmp == 1);
//       TypeLetter(letter);
//     }
//     else if (cmd == 'U') {
//       int number;
//       tmp = scanf("%d", &number);
//       assert(tmp == 1);
//       UndoCommands(number);
//     }
//     else if (cmd == 'P') {
//       int index;
//       char letter;
//       tmp = scanf("%d", &index);
//       assert(tmp == 1);
//       letter = GetLetter(index);
//       printf("%c\n", letter);
//     }
//   }
  
//   puts("Let's test for cheating!!");

//   return 0;

// }

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