oj.uz

Submission #147318

# Submission time Handle Problem Language Result Execution time Memory
147318 2019-08-28T19:59:48 Z Diuven Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 749 ms 93524 KB 
struct node{
	char c='\0';
	int up[21]={}, len=0;
} S[1000010];
int n;
 
void Init(){ n = 0; }
 
void TypeLetter(char L) {
	S[++n].c = L; S[n].len = S[n-1].len+1;
	S[n].up[0] = n-1;
	for(int i=1; i<=20; i++) S[n].up[i] = S[S[n].up[i-1]].up[i-1];
}
 
void UndoCommands(int U) {
	node &pv=S[n-U], &nw = S[n+1]; n++;
	nw.c = pv.c, nw.len = pv.len;
	for(int i=0; i<=20; i++) nw.up[i] = pv.up[i];
}
 
char GetLetter(int P) {
	int d = S[n].len-1-P, v = n;
	for(int i=20; i>=0; i--) if(d>=(1<<i))
		d-=(1<<i), v = S[v].up[i];
	return S[v].c;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 392 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 356 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 788 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 792 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 68492 KB Output is correct
2 Correct 702 ms 83124 KB Output is correct
3 Correct 418 ms 83160 KB Output is correct
4 Correct 504 ms 88324 KB Output is correct
5 Correct 489 ms 77220 KB Output is correct
6 Correct 468 ms 89792 KB Output is correct
7 Correct 543 ms 79104 KB Output is correct
8 Correct 631 ms 87928 KB Output is correct
9 Correct 611 ms 83920 KB Output is correct
10 Correct 275 ms 93524 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 63956 KB Output is correct
2 Correct 698 ms 56572 KB Output is correct
3 Correct 415 ms 70604 KB Output is correct
4 Correct 402 ms 63248 KB Output is correct
5 Correct 475 ms 80816 KB Output is correct
6 Correct 442 ms 83232 KB Output is correct
7 Correct 491 ms 83320 KB Output is correct
8 Correct 662 ms 71880 KB Output is correct
9 Correct 749 ms 68948 KB Output is correct
10 Correct 268 ms 92408 KB Output is correct