oj.uz

Submission #18853

# Submission time Handle Problem Language Result Execution time Memory
18853 2016-02-16T02:31:12 Z suhgyuho_william Crayfish scrivener (IOI12_scrivener) C++
100 / 100
 462 ms 95804 KB 
#include <stdio.h>

int rear,cnt;
int par[1000010][22];
int next[1000010];
int many[1000010];
char a[1000010];

void Init(){
	rear = cnt = 0;
}

void TypeLetter(char L) {
	int i;

	rear++; cnt++;
	next[cnt] = rear;
	a[rear] = L;
	par[rear][0] = next[cnt-1];
	for(i=1; i<=19; i++){
		par[rear][i] = par[par[rear][i-1]][i-1];
	}
	many[cnt] = many[cnt-1]+1;
}

void UndoCommands(int U) {
	cnt++;
	next[cnt] = next[cnt-U-1];
	many[cnt] = many[cnt-U-1];
}

char GetLetter(int P) {
	int i,x;
	int ans;

	ans = next[cnt];
	x = many[cnt]-(P+1);
	//printf("%d %d\n",ans,x);
	for(i=19; i>=0; i--){
		if(x >= (1 << i)){
			ans = par[ans][i];
			x -= (1 << i);
		}
	}
	return a[ans];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 95804 KB Output is correct
2 Correct 363 ms 95804 KB Output is correct
3 Correct 294 ms 95804 KB Output is correct
4 Correct 300 ms 95804 KB Output is correct
5 Correct 345 ms 95804 KB Output is correct
6 Correct 289 ms 95804 KB Output is correct
7 Correct 332 ms 95804 KB Output is correct
8 Correct 325 ms 95804 KB Output is correct
9 Correct 391 ms 95804 KB Output is correct
10 Correct 212 ms 95804 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 95804 KB Output is correct
2 Correct 426 ms 95804 KB Output is correct
3 Correct 297 ms 95804 KB Output is correct
4 Correct 324 ms 95804 KB Output is correct
5 Correct 311 ms 95804 KB Output is correct
6 Correct 318 ms 95804 KB Output is correct
7 Correct 324 ms 95804 KB Output is correct
8 Correct 374 ms 95804 KB Output is correct
9 Correct 462 ms 95804 KB Output is correct
10 Correct 208 ms 95804 KB Output is correct