oj.uz

Submission #231408

# Submission time Handle Problem Language Result Execution time Memory
231408 2020-05-13T13:59:25 Z Fasho Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 619 ms 100728 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 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 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 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 6 ms 768 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 896 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 7 ms 896 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 72316 KB Output is correct
2 Correct 456 ms 87672 KB Output is correct
3 Correct 392 ms 86904 KB Output is correct
4 Correct 422 ms 90964 KB Output is correct
5 Correct 452 ms 80504 KB Output is correct
6 Correct 362 ms 94860 KB Output is correct
7 Correct 478 ms 81272 KB Output is correct
8 Correct 420 ms 91512 KB Output is correct
9 Correct 456 ms 87932 KB Output is correct
10 Correct 287 ms 98936 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 69752 KB Output is correct
2 Correct 572 ms 61540 KB Output is correct
3 Correct 428 ms 77048 KB Output is correct
4 Correct 441 ms 68728 KB Output is correct
5 Correct 396 ms 88056 KB Output is correct
6 Correct 449 ms 91000 KB Output is correct
7 Correct 438 ms 90744 KB Output is correct
8 Correct 619 ms 78456 KB Output is correct
9 Correct 605 ms 75128 KB Output is correct
10 Correct 291 ms 100728 KB Output is correct