oj.uz

Submission #469837

# Submission time Handle Problem Language Result Execution time Memory
469837 2021-09-02T05:21:30 Z wind_reaper Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 519 ms 67268 KB 
const int MXN = 1000001;

char s[MXN];
int up[20][MXN], D[MXN], p[MXN];
int idx = 0, c = 0;

void Init(){}

void TypeLetter(char L){
	s[++idx] = L;
	up[0][idx] = p[c];
	D[idx] = D[p[c]] + 1;
	p[++c] = idx;
	for(int i = 1; i < 20; i++) up[i][idx] = up[i-1][up[i-1][idx]];
}

void UndoCommands(int U){
	++c;
	p[c] = p[c-U-1];
}

char GetLetter(int P){
	int v = p[c]; 
	++P;
	for(int i = 19; i >= 0; --i) if((D[v] - P) & (1 << i)) v = up[i][v];
	return s[v];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 54504 KB Output is correct
2 Correct 299 ms 60896 KB Output is correct
3 Correct 289 ms 60532 KB Output is correct
4 Correct 277 ms 50592 KB Output is correct
5 Correct 363 ms 53296 KB Output is correct
6 Correct 260 ms 65804 KB Output is correct
7 Correct 335 ms 35892 KB Output is correct
8 Correct 289 ms 50688 KB Output is correct
9 Correct 329 ms 67268 KB Output is correct
10 Correct 214 ms 50268 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 47500 KB Output is correct
2 Correct 519 ms 44084 KB Output is correct
3 Correct 289 ms 48108 KB Output is correct
4 Correct 344 ms 38508 KB Output is correct
5 Correct 258 ms 51480 KB Output is correct
6 Correct 269 ms 48664 KB Output is correct
7 Correct 278 ms 51524 KB Output is correct
8 Correct 391 ms 28336 KB Output is correct
9 Correct 462 ms 45572 KB Output is correct
10 Correct 210 ms 49804 KB Output is correct