Submission #108230

#	Time	Username	Problem	Language	Result	Execution time	Memory
108230		SecretAgent007	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	605 ms	98988 KiB

scrivener

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

vector< vector< int > > parents(21, vector< int > (1000009,-1));

int curr = 0;

vector< int > v(1000009);

vector< int > depth(1000009);

vector< char > letter(1000009);

void Init(){
	
}

void TypeLetter(char c){
	curr++;
	
	v[curr] = curr;
	depth[curr] = depth[v[curr-1]]+1;
	letter[curr] = c;
	parents[0][curr] = v[curr-1];
	
	for(int i = 1; i < 21; i++){
		
		if(parents[i-1][curr] != -1){
			parents[i][curr] = parents[i-1][parents[i-1][curr]];
		}
		
	}
}

void UndoCommands(int n){
	v[curr+1] = v[curr-n];
	curr++;
}

char GetLetter(int n){
	
	int jump = depth[v[curr]]-n-1;
	
	int nb = v[curr];
	
	for(int i = 0; i < 21; i++){
		if((1<<i) & jump){
			nb = parents[i][nb];
		}
	}
	
	return letter[nb];
	
}
/*
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	char c;
	while(cin >> c){
		
		if(c == 'T'){
		
			char a;
			cin >> a;
			TypeLetter(a);
		
		}else if(c == 'G'){
		
			int a;
			cin >> a;
			cout << getLetter(a) << endl;
			
		}else{
		
			int a;
			cin >> a;
			UndoCommands(a);

		}
		
	}
}
*/

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