oj.uz

Submission #68079

# Submission time Handle Problem Language Result Execution time Memory
68079 2018-08-15T21:28:58 Z naderjemel Crayfish scrivener (IOI12_scrivener) C++17
60 / 100
 1000 ms 212564 KB 
#include <bits/stdc++.h>
using namespace std;
const int LOG = 21;
struct node
{
	char c; int s;
	node *anc[LOG];
	node(){
		for(int i=0;i<LOG;i++) anc[i] = NULL;
		s=0;
	}
}*tree [1000005];

int id;
void Init(){
	id=1;
	tree[0] = new node();

}
void TypeLetter(char L) {
	int n=id++;
	tree[n] = new node();
	tree[n]->s = tree[n-1]->s+1;
	tree[n]->c = L;
	tree[n]->anc[0]=tree[n-1];
	for(int i=1;i<LOG;i++) tree[n]->anc[i] = (tree[n]->anc[i-1]) ? (tree[n]->anc[i-1])->anc[i-1] : NULL; 
}

void UndoCommands(int U) {
	int ret=id-1-U;
	int n=id++;
	tree[n]=tree[ret];
}


char GetLetter(int P) {
	int n=id-1;
	node *h = new node();
	h=tree[n];
	int up=tree[n]->s - 1 - P;
	for(int i=LOG-1;i>=0;i--){
		if(up - (1<<i) >= 0){
			up-=(1<<i);
			h=h->anc[i];
		}
	}
	return h->c;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 536 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 768 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1056 KB Output is correct
2 Correct 6 ms 1448 KB Output is correct
3 Correct 5 ms 1448 KB Output is correct
4 Correct 5 ms 1516 KB Output is correct
5 Correct 4 ms 1556 KB Output is correct
6 Correct 6 ms 1716 KB Output is correct
7 Correct 5 ms 1868 KB Output is correct
8 Correct 5 ms 1868 KB Output is correct
9 Correct 6 ms 1868 KB Output is correct
10 Correct 4 ms 1868 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 865 ms 136036 KB Output is correct
2 Correct 823 ms 141000 KB Output is correct
3 Correct 589 ms 144868 KB Output is correct
4 Correct 492 ms 144868 KB Output is correct
5 Correct 606 ms 169836 KB Output is correct
6 Correct 758 ms 175992 KB Output is correct
7 Correct 676 ms 175992 KB Output is correct
8 Correct 839 ms 175992 KB Output is correct
9 Correct 804 ms 201600 KB Output is correct
10 Correct 333 ms 201600 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 201600 KB Output is correct
2 Execution timed out 1010 ms 212564 KB Time limit exceeded
3 Halted 0 ms 0 KB -