Submission #241663

#	Time	Username	Problem	Language	Result	Execution time	Memory
241663		kshitij_sodani	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	770 ms	94456 KiB

scrivener

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40