Submission #260235

#	Time	Username	Problem	Language	Result	Execution time	Memory
260235		youssefbou62	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	595 ms	262148 KiB

scrivener

#include <bits/stdc++.h>

#define push_back pb

using namespace std ; 

const int MAXN = 1e6+6 ; 

int state , cnt , par[MAXN][20]; 
map<int,string> ans; 
void Init() {

}

void new_state(int s){
	for(int i=1;i<19;i++){
		par[s][i] = par[par[s][i-1]][i-1]; 
	}
  cerr << "current answer: " << ans[state] << endl; 
}

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) {

  ans[cnt] = ans[state]+L; 
  par[cnt][0] = state ; 
  state = cnt ;
  cnt ++ ; 
new_state(state); 
}

void UndoCommands(int U) {
	int u = kth_anc(state,U) ; 
	// for(int k = 0 ; k < U ; k++ ){
	// 	u = par[u] ; 
	// }
	par[cnt][0] = state ; 
	
	state = cnt ; 
	ans[state] = ans[u] ; 
	cnt ++ ;  
	new_state(state);
}

char GetLetter(int P) {

  return ans[state][P];

}


// 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: 0 / 26
• Subtask 5: 0 / 40