oj.uz

Submission #94647

# Submission time Handle Problem Language Result Execution time Memory
94647 2019-01-22T05:23:08 Z Retro3014 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 841 ms 70252 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define MAX_N 1000000
#define MAX_LN 20
vector<char> c;
int idx[MAX_N+1];
int fr[MAX_N+1][MAX_LN+1];
int ln[MAX_N+1];
int index=0;
int t = 0;

void Init(){
	c.clear();
	ln[0] = -1;
	index = t = 0;
}

void TypeLetter(char L) {
	//cout<<index<<endl;
	fr[c.size()][0] = index;
	ln[c.size()] = ln[index]+1;
	index = c.size();
	c.push_back(L);
	for(int i=1; i<=MAX_LN; i++){
		fr[index][i] = fr[fr[index][i-1]][i-1];
	}
	idx[t++] = index;
}

void UndoCommands(int U) {
	//cout<<index<<endl;
	index = idx[t-U-1];
	idx[t++] = index;
}

char GetLetter(int P) {
	//cout<<index<<endl;
	int now = index;
	P = ln[now] - P;
	int k = (1<<20);
	for(int i=20; i>=0; i--){
		if(k<=P){
			P-=k;
			now = fr[now][i];
		}
		k = (k>>1);
	}
	//cout<<"*"<<now<<endl;
	return c[now];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 57544 KB Output is correct
2 Correct 656 ms 63532 KB Output is correct
3 Correct 401 ms 63084 KB Output is correct
4 Correct 378 ms 52596 KB Output is correct
5 Correct 503 ms 55532 KB Output is correct
6 Correct 355 ms 68592 KB Output is correct
7 Correct 403 ms 37236 KB Output is correct
8 Correct 343 ms 52724 KB Output is correct
9 Correct 656 ms 70252 KB Output is correct
10 Correct 204 ms 52224 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 50620 KB Output is correct
2 Correct 750 ms 46068 KB Output is correct
3 Correct 365 ms 50036 KB Output is correct
4 Correct 344 ms 39928 KB Output is correct
5 Correct 385 ms 53488 KB Output is correct
6 Correct 392 ms 50676 KB Output is correct
7 Correct 455 ms 53748 KB Output is correct
8 Correct 591 ms 29408 KB Output is correct
9 Correct 841 ms 47472 KB Output is correct
10 Correct 203 ms 51888 KB Output is correct