oj.uz

Submission #241663

# Submission time Handle Problem Language Result Execution time Memory
241663 2020-06-25T06:23:14 Z kshitij_sodani Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 770 ms 94456 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

//#define endl '\n'
int ind[1000001];
int back[1000001];
int st[1000001];
int cc[1000001];
int co=1;
int cur[1000001][20];
char cop[1000001];

/*int find(int no){
	if(st[no]==1){
		return no;
	}
	par[no]=find(par[no]);
	return no;
}*/

void Init() {
	/*for(int j=0;j<20;j++){
		cur[j][0]=-1;
	}*/
	//memset(cur,-1,sizeof(cur));
}

void TypeLetter(char L) {
	cop[co]=L;
	if(co>0){
		ind[co]=back[co-1];
		cc[co]=1+cc[ind[co]];
		cur[co][0]=ind[co];
		for(int j=1;j<20;j++){
			if(cur[co][j-1]==-1){
				break;
			}
			cur[co][j]=cur[cur[co][j-1]][j-1];
		}
	}
	else{
		cc[co]=1;

	}
	back[co]=co;
	co+=1;

}

void UndoCommands(int u) {
	back[co]=back[co-u-1];
	//cout<<co<<","<<back[co-u]<<endl;

	co+=1;
}

char GetLetter(int p) {
	int la=back[co-1];
	if(p==cc[la]-1){
	//	cout<<cop[la]<<endl;
		return cop[la];
	}
	int jj=la;
	int x=cc[la]-p-1;
	for(int j=19;j>=0;j--){
		if((x&(1<<j))){
			jj=cur[jj][j];
		}
	}
	
	
	//cout<<cop[jj]<<endl;
	return cop[jj];
}





/*
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
*/
/*
g++ -DEVAL -Wall -static -O2 -o aa grader1.cpp scrivener.cpp
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 65564 KB Output is correct
2 Correct 464 ms 83960 KB Output is correct
3 Correct 404 ms 84092 KB Output is correct
4 Correct 400 ms 89336 KB Output is correct
5 Correct 437 ms 78072 KB Output is correct
6 Correct 391 ms 91016 KB Output is correct
7 Correct 448 ms 79996 KB Output is correct
8 Correct 399 ms 88824 KB Output is correct
9 Correct 448 ms 84856 KB Output is correct
10 Correct 291 ms 94456 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 60152 KB Output is correct
2 Correct 732 ms 57340 KB Output is correct
3 Correct 400 ms 71416 KB Output is correct
4 Correct 427 ms 63992 KB Output is correct
5 Correct 398 ms 81540 KB Output is correct
6 Correct 426 ms 84140 KB Output is correct
7 Correct 413 ms 84132 KB Output is correct
8 Correct 770 ms 72696 KB Output is correct
9 Correct 620 ms 69676 KB Output is correct
10 Correct 292 ms 93180 KB Output is correct