oj.uz

Submission #241593

# Submission time Handle Problem Language Result Execution time Memory
241593 2020-06-24T16:00:45 Z johutha Crayfish scrivener (IOI12_scrivener) C++17
34 / 100
 1000 ms 228192 KB 
#pragma GCC optimize ("O3")

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

struct node;

using node_ptr = node*;

struct node
{
	int len;
	char l;
	vector<node_ptr> upread;
	vector<node_ptr> upundo;

	node()
	{
		upread = vector<node_ptr>(22);
		upundo = vector<node_ptr>(22);
		l = '0';
		len = 0;
	}

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

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

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

		for (int i = 21; 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 = 21; 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 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 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 256 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 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 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1152 KB Output is correct
2 Correct 7 ms 1536 KB Output is correct
3 Correct 8 ms 2048 KB Output is correct
4 Correct 8 ms 2304 KB Output is correct
5 Correct 7 ms 1920 KB Output is correct
6 Correct 8 ms 2304 KB Output is correct
7 Correct 7 ms 2048 KB Output is correct
8 Correct 8 ms 2304 KB Output is correct
9 Correct 8 ms 2304 KB Output is correct
10 Correct 8 ms 2432 KB Output is correct

Subtask #4
0 / 26.0

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

Subtask #5
0 / 40.0

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