oj.uz

Submission #393037

# Submission time Handle Problem Language Result Execution time Memory
393037 2021-04-22T15:22:29 Z rainboy Crayfish scrivener (IOI12_scrivener) C
100 / 100
 586 ms 67256 KB 
#define N	1000001
#define LN	19	/* LN = floor(log2(N)) */

int uu[N], pp[N][LN + 1], dd[N], n_, i; char cc[N];

void Init() {
	n_ = 1;
}

void TypeLetter(char c) {
	int l, u;

	i++;
	u = uu[i] = n_++;
	cc[u] = c, pp[u][0] = uu[i - 1], dd[u] = dd[uu[i - 1]] + 1;
	for (l = 1; 1 << l <= dd[u]; l++)
		pp[u][l] = pp[pp[u][l - 1]][l - 1];
}

void UndoCommands(int k) {
	i++, uu[i] = uu[i - 1 - k];
}

char GetLetter(int d) {
	int u = uu[i], l;

	d++;
	for (l = LN; l >= 0; l--)
		if (dd[u] - d >= 1 << l)
			u = pp[u][l];
	return cc[u];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 460 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 55096 KB Output is correct
2 Correct 395 ms 60780 KB Output is correct
3 Correct 362 ms 60336 KB Output is correct
4 Correct 345 ms 50488 KB Output is correct
5 Correct 399 ms 53156 KB Output is correct
6 Correct 309 ms 65700 KB Output is correct
7 Correct 358 ms 35744 KB Output is correct
8 Correct 383 ms 50508 KB Output is correct
9 Correct 406 ms 67256 KB Output is correct
10 Correct 240 ms 49988 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 48448 KB Output is correct
2 Correct 586 ms 44056 KB Output is correct
3 Correct 368 ms 47952 KB Output is correct
4 Correct 440 ms 38204 KB Output is correct
5 Correct 312 ms 51268 KB Output is correct
6 Correct 319 ms 48500 KB Output is correct
7 Correct 333 ms 51408 KB Output is correct
8 Correct 433 ms 28180 KB Output is correct
9 Correct 512 ms 45452 KB Output is correct
10 Correct 263 ms 49728 KB Output is correct