oj.uz

Submission #241597

# Submission time Handle Problem Language Result Execution time Memory
241597 2020-06-24T16:32:37 Z johutha Crayfish scrivener (IOI12_scrivener) C++17
34 / 100
 1000 ms 165012 KB 
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

int upr[1000001][21];
int upu[1000001][21];
char ch[1000001];
int len[1000001];
int cnt = 0;
int bck = 0;

void Init()
{
	cnt = 1;
	bck = 0;
	for (int i = 0; i < 21; i++)
	{
		upr[0][i] = 0;
		upu[0][i] = 0;
	}
}

void update(int id)
{
	for (int i = 1; i < 21; i++)
	{
		upu[id][i] = upu[upu[id][i - 1]][i - 1];
		upr[id][i] = upr[upr[id][i - 1]][i - 1];
	}
}

void TypeLetter(char L)
{
	ch[cnt] = L;
	len[cnt] = len[bck] + 1;
	upu[cnt][0] = bck;
	upr[cnt][0] = bck;
	update(cnt);
	bck = cnt;
	cnt++;
}

void UndoCommands(signed U)
{
	int ld = bck;
	for (int i = 0; i < 21; i++)
	{
		if (U & (1<<i))
		{
			ld = upu[ld][i];
		}
	}
	ch[cnt] = ch[ld];
	upr[cnt][0] = upr[ld][0];
	upu[cnt][0] = bck;
	len[cnt] = len[ld];
	update(cnt);
	bck = cnt;
	cnt++;
}

char GetLetter(signed P)
{
	int u = len[bck] - 1 - P;
	int c = bck;

	for (int i = 0; i < 21; i++)
	{
		if (u & (1<<i))
		{
			c = upr[c][i];
		}
	}
	return ch[c];
}

Subtask #1
5.0 / 5.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 121452 KB Output is correct
2 Correct 679 ms 152184 KB Output is correct
3 Correct 689 ms 151932 KB Output is correct
4 Correct 849 ms 160376 KB Output is correct
5 Correct 701 ms 140664 KB Output is correct
6 Correct 592 ms 165012 KB Output is correct
7 Execution timed out 1100 ms 141308 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 111064 KB Output is correct
2 Correct 809 ms 100728 KB Output is correct
3 Correct 665 ms 127608 KB Output is correct
4 Correct 698 ms 112120 KB Output is correct
5 Correct 572 ms 147064 KB Output is correct
6 Correct 652 ms 151928 KB Output is correct
7 Correct 652 ms 151804 KB Output is correct
8 Execution timed out 1092 ms 111864 KB Time limit exceeded
9 Halted 0 ms 0 KB -