Submission #286601

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
286601	2020-08-30T15:18:42 Z	amiratou	Crayfish scrivener (IOI12_scrivener)	C++17	74 / 100	1000 ms	126968 KB

scrivener

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int LOG=20,MX=(int)(1e6+7);

int up[MX][LOG],d[MX],idx;
char car[MX];
vector<int> vec[MX];
 
void Init() {
 
}
 
void TypeLetter(char L) {
	vec[idx].pb(idx+1);
	d[idx+1]=d[idx]+1;
	up[idx+1][0]=idx;
	for (int i = 1; i < LOG; ++i)
		up[idx+1][i]=up[up[idx+1][i-1]][i-1];
	car[idx+1]=L;
	idx++;
}
 
void UndoCommands(int U) {
	d[idx+1]=d[idx-U];
	up[idx+1][0]=up[idx-U][0];
	for (int i = 1; i < LOG; ++i)
		up[idx+1][i]=up[up[idx+1][i-1]][i-1];
	if(idx!=U){
		vec[up[idx-U][0]].pb(idx+1);
		car[idx+1]=car[idx-U];
	}
	idx++;
}
 
char GetLetter(int P) {
	int k=d[idx]-1-P,a=idx;
	for (int i = 0; i < LOG; ++i)
		if((k>>i)&1)a=up[a][i];
	return car[a];
 
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	23808 KB	Output is correct
2	Correct	17 ms	23808 KB	Output is correct
3	Correct	17 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	17 ms	23808 KB	Output is correct
6	Correct	19 ms	23936 KB	Output is correct
7	Correct	18 ms	23936 KB	Output is correct
8	Correct	17 ms	23808 KB	Output is correct
9	Correct	18 ms	23808 KB	Output is correct
10	Correct	17 ms	23808 KB	Output is correct

Subtask #2

7.0 / 7.0

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

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	24008 KB	Output is correct
2	Correct	19 ms	24192 KB	Output is correct
3	Correct	19 ms	24320 KB	Output is correct
4	Correct	19 ms	24320 KB	Output is correct
5	Correct	19 ms	24224 KB	Output is correct
6	Correct	19 ms	24320 KB	Output is correct
7	Correct	19 ms	24320 KB	Output is correct
8	Correct	19 ms	24320 KB	Output is correct
9	Correct	19 ms	24320 KB	Output is correct
10	Correct	20 ms	24320 KB	Output is correct

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	479 ms	102796 KB	Output is correct
2	Correct	593 ms	117880 KB	Output is correct
3	Correct	571 ms	116856 KB	Output is correct
4	Correct	699 ms	116728 KB	Output is correct
5	Correct	526 ms	108536 KB	Output is correct
6	Correct	459 ms	125432 KB	Output is correct
7	Execution timed out	1008 ms	103544 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	562 ms	95352 KB	Output is correct
2	Correct	608 ms	85492 KB	Output is correct
3	Correct	593 ms	100088 KB	Output is correct
4	Correct	622 ms	88428 KB	Output is correct
5	Correct	475 ms	111140 KB	Output is correct
6	Correct	509 ms	112596 KB	Output is correct
7	Correct	512 ms	113400 KB	Output is correct
8	Correct	993 ms	94304 KB	Output is correct
9	Correct	843 ms	101840 KB	Output is correct
10	Correct	380 ms	126968 KB	Output is correct