oj.uz

Submission #834801

# Submission time Handle Problem Language Result Execution time Memory
834801 2023-08-22T19:47:33 Z happypotato Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 430 ms 234016 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int flog2(int x) {
	return 31 - __builtin_clz(x);
}
bool ispow2(int x) {
	return (x == (1 << flog2(x)));
}
struct Trie {
	char c;
	int len;
	Trie *lptr, *rptr;
	Trie(char cur = '.'): c(cur), len((cur != '.')), lptr(nullptr), rptr(nullptr) {};
};
vector<Trie*> ver;
Trie *cur, *pre;
void Init() {
	ver.pb(nullptr);
}
 
void TypeLetter(char L) {
	cur = new Trie();
	pre = ver.back();
	ver.pb(cur);
	while (pre != nullptr) {
		cur->len = pre->len + 1;
		if (ispow2(pre->len)) {
			cur->lptr = pre;
			cur->rptr = new Trie(L);
			return;
		}
		cur->lptr = pre->lptr;
		cur->rptr = new Trie();
		cur = cur->rptr;
		pre = pre->rptr;
	}
	cur->c = L;
	cur->len = 1;
}
 
void UndoCommands(int U) {
	int ptr = (int)(ver.size()) - 1 - U;
	ver.pb(ver[ptr]);
}
 
char GetLetter(int P) {
	cur = ver.back();
	while (cur->len != 1) {
		if (P < cur->lptr->len) {
			cur = cur->lptr;
		} else {
			P -= cur->lptr->len;
			cur = cur->rptr;
		}
	}
	return cur->c;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 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 596 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 852 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 312 ms 191012 KB Output is correct
2 Correct 350 ms 213008 KB Output is correct
3 Correct 308 ms 208580 KB Output is correct
4 Correct 326 ms 183516 KB Output is correct
5 Correct 352 ms 169784 KB Output is correct
6 Correct 344 ms 232904 KB Output is correct
7 Correct 341 ms 109976 KB Output is correct
8 Correct 331 ms 173732 KB Output is correct
9 Correct 368 ms 234016 KB Output is correct
10 Correct 265 ms 197412 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 159164 KB Output is correct
2 Correct 386 ms 138796 KB Output is correct
3 Correct 341 ms 173876 KB Output is correct
4 Correct 326 ms 129188 KB Output is correct
5 Correct 287 ms 173600 KB Output is correct
6 Correct 299 ms 152968 KB Output is correct
7 Correct 306 ms 172564 KB Output is correct
8 Correct 348 ms 80312 KB Output is correct
9 Correct 430 ms 150972 KB Output is correct
10 Correct 261 ms 195832 KB Output is correct