oj.uz

Submission #108230

# Submission time Handle Problem Language Result Execution time Memory
108230 2019-04-28T10:03:12 Z SecretAgent007 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 605 ms 98988 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 91444 KB Output is correct
2 Correct 96 ms 91532 KB Output is correct
3 Correct 87 ms 91312 KB Output is correct
4 Correct 86 ms 91328 KB Output is correct
5 Correct 89 ms 91316 KB Output is correct
6 Correct 96 ms 91444 KB Output is correct
7 Correct 89 ms 91416 KB Output is correct
8 Correct 110 ms 91320 KB Output is correct
9 Correct 97 ms 91316 KB Output is correct
10 Correct 87 ms 91392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 91340 KB Output is correct
2 Correct 91 ms 91444 KB Output is correct
3 Correct 87 ms 91364 KB Output is correct
4 Correct 89 ms 91316 KB Output is correct
5 Correct 87 ms 91444 KB Output is correct
6 Correct 101 ms 91316 KB Output is correct
7 Correct 84 ms 91316 KB Output is correct
8 Correct 87 ms 91388 KB Output is correct
9 Correct 100 ms 91316 KB Output is correct
10 Correct 86 ms 91444 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 91376 KB Output is correct
2 Correct 96 ms 91392 KB Output is correct
3 Correct 92 ms 91444 KB Output is correct
4 Correct 89 ms 91444 KB Output is correct
5 Correct 93 ms 91444 KB Output is correct
6 Correct 90 ms 91536 KB Output is correct
7 Correct 95 ms 91444 KB Output is correct
8 Correct 91 ms 91448 KB Output is correct
9 Correct 86 ms 91444 KB Output is correct
10 Correct 90 ms 91444 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 94036 KB Output is correct
2 Correct 460 ms 95404 KB Output is correct
3 Correct 421 ms 96416 KB Output is correct
4 Correct 447 ms 97708 KB Output is correct
5 Correct 425 ms 96536 KB Output is correct
6 Correct 323 ms 95788 KB Output is correct
7 Correct 457 ms 97708 KB Output is correct
8 Correct 374 ms 96944 KB Output is correct
9 Correct 469 ms 96172 KB Output is correct
10 Correct 259 ms 95480 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 94696 KB Output is correct
2 Correct 572 ms 97608 KB Output is correct
3 Correct 455 ms 97196 KB Output is correct
4 Correct 535 ms 98988 KB Output is correct
5 Correct 324 ms 96352 KB Output is correct
6 Correct 339 ms 96108 KB Output is correct
7 Correct 365 ms 96356 KB Output is correct
8 Correct 605 ms 97964 KB Output is correct
9 Correct 590 ms 97592 KB Output is correct
10 Correct 258 ms 95548 KB Output is correct