oj.uz

Submission #285261

# Submission time Handle Problem Language Result Execution time Memory
285261 2020-08-28T14:10:16 Z TMJN Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 628 ms 94456 KB 
int dp[1000000][21];
int len[1000000];
char c[1000000];
int t[1000000];
int cnt;

void Init() {
	len[0]=-1;
}

void TypeLetter(char L) {
	cnt++;
	len[cnt]=len[cnt-1]+1;
	t[cnt]=cnt;
	c[cnt]=L;
	dp[cnt][0]=t[cnt-1];
	for(int i=0;i<=19;i++){
		dp[cnt][i+1]=dp[dp[cnt][i]][i];
	}
}

void UndoCommands(int U) {
	cnt++;
	len[cnt]=len[cnt-U-1];
	t[cnt]=t[cnt-U-1];
	for(int i=0;i<19;i++){
		dp[cnt][i+1]=dp[dp[cnt][i]][i];
	}
}

char GetLetter(int P) {
	int p=t[cnt];
	int l=len[p];
	for(int i=20;i>=0;i--){
		if(l-(1<<i)>=P){
			l-=(1<<i);
			p=dp[p][i];
		}
	}
	return c[p];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 65528 KB Output is correct
2 Correct 445 ms 83836 KB Output is correct
3 Correct 452 ms 84092 KB Output is correct
4 Correct 418 ms 89548 KB Output is correct
5 Correct 455 ms 78072 KB Output is correct
6 Correct 355 ms 90880 KB Output is correct
7 Correct 520 ms 79992 KB Output is correct
8 Correct 425 ms 88824 KB Output is correct
9 Correct 445 ms 84728 KB Output is correct
10 Correct 298 ms 94456 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 60024 KB Output is correct
2 Correct 582 ms 57080 KB Output is correct
3 Correct 402 ms 71416 KB Output is correct
4 Correct 428 ms 63864 KB Output is correct
5 Correct 408 ms 81400 KB Output is correct
6 Correct 448 ms 84088 KB Output is correct
7 Correct 444 ms 83960 KB Output is correct
8 Correct 628 ms 72632 KB Output is correct
9 Correct 628 ms 69764 KB Output is correct
10 Correct 301 ms 93432 KB Output is correct