oj.uz

Submission #594910

# Submission time Handle Problem Language Result Execution time Memory
594910 2022-07-13T06:55:50 Z 8e7 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 331 ms 67968 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
int pos[maxn], len[maxn], anc[20][maxn];
char c[maxn];
int ti = 1, st = 0;

void Init() {}

void TypeLetter(char L) {
	int prv = pos[ti-1];
	st++;
	anc[0][st] = prv;
	for (int i = 1;i < 20;i++) anc[i][st] = anc[i-1][anc[i-1][st]];
	len[ti] = len[ti-1] + 1;
	pos[ti] = st;
	c[st] = L;
	ti++;
}

void UndoCommands(int U) {
	pos[ti] = pos[ti - U - 1];	
	len[ti] = len[ti - U - 1];	
	ti++;
}

char GetLetter(int P) {
	int dis = len[ti-1] - P - 1;
	
	int cur = pos[ti-1], cnt = 0;
	while (dis) {
		if (dis & 1) cur = anc[cnt][cur];
		cnt++, dis >>= 1;
	}
	return c[cur];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 580 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 55848 KB Output is correct
2 Correct 261 ms 61840 KB Output is correct
3 Correct 238 ms 61472 KB Output is correct
4 Correct 252 ms 52300 KB Output is correct
5 Correct 255 ms 54348 KB Output is correct
6 Correct 206 ms 66812 KB Output is correct
7 Correct 228 ms 37816 KB Output is correct
8 Correct 205 ms 52252 KB Output is correct
9 Correct 258 ms 67968 KB Output is correct
10 Correct 180 ms 52144 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 49180 KB Output is correct
2 Correct 278 ms 44584 KB Output is correct
3 Correct 244 ms 49028 KB Output is correct
4 Correct 254 ms 39636 KB Output is correct
5 Correct 221 ms 52764 KB Output is correct
6 Correct 237 ms 50120 KB Output is correct
7 Correct 195 ms 52992 KB Output is correct
8 Correct 309 ms 30240 KB Output is correct
9 Correct 331 ms 46624 KB Output is correct
10 Correct 171 ms 51916 KB Output is correct