Submission #231408

#	Time	Username	Problem	Language	Result	Execution time	Memory
231408		Fasho	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	619 ms	100728 KiB

scrivener

#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
using namespace std;


char last,flag=1;

ll dad[N],cnt,sz[N],pw[N];

int jumpvertex[N][21];

char s[N];
vector<char> v;


ll find(int x)
{
	if(dad[x]==x)
		return x;
	return dad[x]=find(dad[x]);
}

void unite(int x,int y)
{
	int dx=find(x);
	int dy=find(y);
	dad[dy]=dx;

}

void Init() 
{
	pw[0]=1;
	fo(i,1,20)
	pw[i]=pw[i-1]*2;
}


void TypeLetter(char L) {

	flag=0;

	s[++cnt]=L;
	dad[cnt]=cnt;
  

  last = L;
  sz[cnt]=sz[find(cnt-1)]+1;
  ll x=cnt;
  ll y=find(x-1);
  jumpvertex[x][0]=y;
  fo(i,1,20)
  jumpvertex[x][i]=jumpvertex[jumpvertex[x][i-1]][i-1];


}

void UndoCommands(int U) 
{
	flag=0;
	cnt++;
	dad[cnt]=cnt;
	unite(cnt-U-1,cnt);
}

// char GetLetter(int P) {
// 	ll x=cnt;
// 	if(flag==1)
// 		return v[P];
// 	flag=1;
// 	v.clear();
// 	while(x>0)
// 	{
// 		x=find(x);
// 		v.pb(s[x]);
// 		x--;
// 	}

// 	reverse(v.begin(), v.end());
// 	return  v[P];

// }

char GetLetter(int P) 
{
	P++;
	ll x=find(cnt);
	ll y=sz[x]-P;
	// while(y)
	// {
	// cerr<<"[d2]"<<sp<<x<<sp<<y<<endl;
	for(int i=20;i>=0;i--)
	{
		if(pw[i]<=y)
		{
			// cerr<<"[d3]"<<sp<<i<<endl;
			y-=pw[i];
			x=jumpvertex[x][i];
		}
	}
	// cerr<<endl;
	// fo(i,1,cnt)
	// {
	// 	cout<<"[d]"<<sp<<i<<endl;
	// 	fo(j,0,3)
	// 	{
	// 		cout<<jumpvertex[i][j]<<sp;
	// 	}
	// 	cout<<endl;

	// }
	// cout<<endl;
	// cerr<<x<<sp;
	return s[x];
	// }
}

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