Submission #760652

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
760652	2023-06-18T05:01:37 Z	ymm	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	412 ms	89464 KB

scrivener

#include <bits/stdc++.h>
#define Loop(x,l,r)  for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;

const int lg = 20;
const int N = 1<<lg;

struct {
	int anc[lg];
	int len;
	char l;
} node[N];
int pos = 0;

void Init() {}

void TypeLetter(char L) {
	int v = pos+1;
	node[v].anc[0] = pos;
	Loop (i,1,lg)
		node[v].anc[i] = node[node[v].anc[i-1]].anc[i-1];
	node[v].len = node[pos].len+1;
	node[v].l = L;
	++pos;
}

void UndoCommands(int U) {
	memcpy(&node[pos+1], &node[pos-U], sizeof(*node));
	++pos;
}

char GetLetter(int P) {
	//string s;
	//for (int v = pos; node[v].l; v = node[v].anc[0])
	//	s += node[v].l;
	//reverse(s.begin(), s.end());
	//cout << s << '\n';
	P = node[pos].len - 1 - P;
	int v = pos;
	LoopR (i,0,lg) {
		if (!(P & (1<<i)))
			continue;
		v = node[v].anc[i];
	}
	return node[v].l;
}

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

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

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	588 KB	Output is correct
3	Correct	2 ms	596 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Correct	2 ms	596 KB	Output is correct
6	Correct	2 ms	724 KB	Output is correct
7	Correct	2 ms	584 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	2 ms	716 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	65672 KB	Output is correct
2	Correct	280 ms	79516 KB	Output is correct
3	Correct	251 ms	79692 KB	Output is correct
4	Correct	262 ms	84776 KB	Output is correct
5	Correct	296 ms	74044 KB	Output is correct
6	Correct	257 ms	86052 KB	Output is correct
7	Correct	286 ms	75852 KB	Output is correct
8	Correct	317 ms	84224 KB	Output is correct
9	Correct	340 ms	80400 KB	Output is correct
10	Correct	176 ms	89464 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	292 ms	61260 KB	Output is correct
2	Correct	347 ms	54348 KB	Output is correct
3	Correct	233 ms	67816 KB	Output is correct
4	Correct	305 ms	60728 KB	Output is correct
5	Correct	246 ms	77288 KB	Output is correct
6	Correct	309 ms	79636 KB	Output is correct
7	Correct	277 ms	79600 KB	Output is correct
8	Correct	324 ms	68936 KB	Output is correct
9	Correct	412 ms	66128 KB	Output is correct
10	Correct	182 ms	88496 KB	Output is correct