oj.uz

Submission #16272

# Submission time Handle Problem Language Result Execution time Memory
16272 2015-08-19T12:14:22 Z comet Crayfish scrivener (IOI12_scrivener) C++
100 / 100
 485 ms 91896 KB 
struct node{
	char t;
	int x,len;
}s[1000000];
int a[1000000][20],sz,cnt;
char b[1000000];
void Init() {}

void TypeLetter(char L){
	int p=0;
	if(sz)p=s[sz-1].len;
	s[sz++]={L,cnt++,p+1};
	b[cnt-1]=L;
	if(sz>1){
		a[cnt-1][0]=s[sz-2].x;
		for(int i=1;i<20;i++)a[cnt-1][i]=a[a[cnt-1][i-1]][i-1];
	}
/*
	for(int i=0;i<sz;i++)printf("%c,%d,%d ",s[i].t,s[i].x,s[i].len);
	puts("");

	int x=s[sz-1].x;
	do{
		printf("%c ",b[x]);
		x=a[x][0];
	}while(x);
	puts("");*/
}

void UndoCommands(int U) {
	s[sz]=s[sz-U-1];
	sz++;
/*
	for(int i=0;i<sz;i++)printf("%c,%d,%d ",s[i].t,s[i].x,s[i].len);
	puts("");
	int x=s[sz-1].x;
	do{
		printf("%c ",b[x]);
		x=a[x][0];
	}while(x);
	puts("");*/
}

char GetLetter(int P) {
	int x=s[sz-1].x;

	P=s[sz-1].len-P;
	for(int i=19;i>=0;i--){
		if(P>(1<<i)){
			P-=(1<<i);
			x=a[x][i];
		}
	}
	return b[x];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 91896 KB Output is correct
2 Correct 411 ms 91896 KB Output is correct
3 Correct 319 ms 91896 KB Output is correct
4 Correct 328 ms 91896 KB Output is correct
5 Correct 342 ms 91896 KB Output is correct
6 Correct 289 ms 91896 KB Output is correct
7 Correct 332 ms 91896 KB Output is correct
8 Correct 298 ms 91896 KB Output is correct
9 Correct 415 ms 91896 KB Output is correct
10 Correct 211 ms 91896 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 91896 KB Output is correct
2 Correct 457 ms 91896 KB Output is correct
3 Correct 318 ms 91896 KB Output is correct
4 Correct 333 ms 91896 KB Output is correct
5 Correct 310 ms 91896 KB Output is correct
6 Correct 320 ms 91896 KB Output is correct
7 Correct 328 ms 91896 KB Output is correct
8 Correct 395 ms 91896 KB Output is correct
9 Correct 485 ms 91896 KB Output is correct
10 Correct 223 ms 91896 KB Output is correct