oj.uz

Submission #241596

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

using namespace std;

struct node;

using node_ptr = node*;

struct node
{
	int len;
	char l;
	node_ptr upread[21];
	node_ptr upundo[21];

	node()
	{
		l = '0';
		len = 0;
		for (int i = 0; i < 21; i++)
		{
			upread[i] = this;
			upundo[i] = this;
		}
	}

	node(char il, node_ptr lr, node_ptr lu) : l(il)
	{
		upread[0] = lr;
		upundo[0] = lu;
		len = lr->len + 1;

		for (int i = 1; i < 21; i++)
		{
			upread[i] = (upread[i - 1] != 0 ? upread[i - 1]->upread[i - 1] : node_ptr());
			upundo[i] = (upundo[i - 1] != 0 ? upundo[i - 1]->upundo[i - 1] : node_ptr());
		}
	}

	node_ptr getundo(int k)
	{
		node_ptr cp = this;

		for (int i = 20; i >= 0; i--)
		{
			if (k & (1ll<<i)) cp = cp->upundo[i];
			assert(cp != 0);
		}
		return cp;
	}

	node_ptr getread(int k)
	{
		node_ptr cp = this;

		for (int i = 20; i >= 0; i--)
		{
			if (k & (1ll<<i)) cp = cp->upread[i];
			assert(cp != 0);
		}
		return cp;
	}
};

node_ptr back;

void Init()
{
	back = new node();
}

void TypeLetter(char L)
{
	back = new node(L, back, back);
}

void UndoCommands(signed U)
{
	node_ptr rep = back->getundo(U);
	back = new node(rep->l, rep->upread[0], back);
}

char GetLetter(signed P)
{
	int ind = back->len - 1 - P;
	node_ptr rd = back->getread(ind);
	return rd->l;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 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 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 6 ms 896 KB Output is correct
2 Correct 7 ms 1280 KB Output is correct
3 Correct 7 ms 1792 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1536 KB Output is correct
6 Correct 7 ms 1920 KB Output is correct
7 Correct 7 ms 1792 KB Output is correct
8 Correct 7 ms 1920 KB Output is correct
9 Correct 7 ms 1792 KB Output is correct
10 Correct 7 ms 1920 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 247416 KB Output is correct
2 Runtime error 955 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 226236 KB Time limit exceeded
2 Halted 0 ms 0 KB -