Submission #911634

#	Time	Username	Problem	Language	Result	Execution time	Memory
911634		Faisal_Saqib	Crayfish scrivener (IOI12_scrivener)	C++17	5 / 100	6 ms	3932 KiB

scrivener

#include <iostream>
using namespace std;
const int N=5001;
const int MAX_T=2*N;
const int LG=21;
int par[MAX_T][LG];
int par_cnt[MAX_T][LG];
int ln[MAX_T];
char op[MAX_T];
int cur_t=1;
void Init()
{
	op[0]='1';
}
void TypeLetter(char L)
{
	// cout<<"insert "<<L<<" tm "<<cur_t<<endl;
	op[cur_t]=L;
	par[cur_t][0]=cur_t-1;
	par_cnt[cur_t][0]=(op[cur_t-1]!='$');
	ln[cur_t]=ln[cur_t-1]+1;
	for(int j=1;j<LG;j++)
	{
		par[cur_t][j]=par[par[cur_t][j-1]][j-1];
		par_cnt[cur_t][j]=par_cnt[par[cur_t][j-1]][j-1]+par_cnt[cur_t][j-1];
	}
	cur_t++;
}
void UndoCommands(int U)
{
	// cout<<"Undo "<<U<<" tm "<<cur_t<<endl;
	op[cur_t]='$';
	ln[cur_t]=ln[cur_t-U-1];
	par[cur_t][0]=cur_t-1-U;
	par_cnt[cur_t][0]=(op[cur_t-1-U]!='$');
	for(int j=1;j<LG;j++)
	{
		par[cur_t][j]=par[par[cur_t][j-1]][j-1];
		par_cnt[cur_t][j]=par_cnt[par[cur_t][j-1]][j-1]+par_cnt[cur_t][j-1];
	}
	cur_t++;
}
char GetLetter(int P)
{
	int cp=cur_t-1;
	int len=ln[cp];
	int wnt=len-P;
	// cout<<"Done\n";
	// cout<<len<<' '<<P<<' '<<wnt<<endl;
	char c='1';
	if(op[cp]!='$')
	{
		wnt--;
		c=op[cp];
	}
	// cout<<"Gojo "<<wnt<<endl;
	for(int j=LG-1;j>=0;j--)
	{
		// cout<<"Minus "<<cp<<' '<<j<<' '<<par_cnt[cp][j]<<endl;
		if(wnt>=(par_cnt[cp][j]))
		{
			wnt-=par_cnt[cp][j];
			cp=par[cp][j];
			c=op[cp];
		}
		// if(op[cp]!='$')
		// {
		// 	wnt--;
		// 	c=op[cp];
		// }
	}	
	// cout<<"HE ";
	// cout<<cp<<endl;
	// cout<<wnt<<endl;
	return c;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40