oj.uz

Submission #131873

# Submission time Handle Problem Language Result Execution time Memory
131873 2019-07-17T20:54:50 Z arthurconmy Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 733 ms 86792 KB 
/* Arthur Conmy / arthurconmy */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;

#define REP(i,a,b) \
for(int i=(a); i<=(b); i++)

#define REPb(i,a,b) \
for(int i=(a); i>=(b); i--)

int p2[20];
int parent[20][1000001];
char letter_pres[1000001];
int cur_len[1000001];
int cur=0;

// vector<int> history;

void Init()
{
	REP(i,0,19)
	{
		parent[0][i]=-1;
	}

	p2[0]=1;

	REP(i,1,19)
	{
		p2[i]=p2[i-1]+p2[i-1];
	}
}

void TypeLetter(char L)
{
	parent[0][cur+1]=cur;
	cur++;

	letter_pres[cur]=L;

	cur_len[cur]=cur_len[cur-1]+1;

	REP(i,1,19)
	{
		parent[i][cur] = parent[i-1][parent[i-1][cur]];
	}
}

void UndoCommands(int U)
{
	int v_copying = cur - U;
	cur++;

	REP(i,0,19)
	{
		parent[i][cur] = parent[i][v_copying];
	}

	letter_pres[cur]=letter_pres[v_copying]; // could get iffy - unitialised char ???
	cur_len[cur]=cur_len[v_copying];
}

char GetLetter(int P) 
{
	int length = cur_len[cur];
	P++; // not zero-indexed anymore

	int v=cur;

	int up_trav = length-P;

	REPb(i,19,0)
	{
		if(up_trav >= p2[i])
		{
			v=parent[i][v];
			up_trav-=p2[i];
		}
	}

	#ifdef ARTHUR_LOCAL
		cout << letter_pres[v] << endl;
	#endif

	return letter_pres[v];
}


// int main()
// {
// 	#ifdef ARTHUR_LOCAL
// 		ifstream cin("input.txt");
// 	#endif

// 	Init();
// 	TypeLetter('a');
// 	TypeLetter('b');
// 	GetLetter(1);
// 	TypeLetter('d');
// 	UndoCommands(2);
// 	UndoCommands(1);
// 	GetLetter(2);
// 	TypeLetter('e');
// 	UndoCommands(1);
// 	UndoCommands(5);
// 	TypeLetter('c');
// 	GetLetter(2);
// 	UndoCommands(2);
// 	GetLetter(2);
// }

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 504 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 936 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 4 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 888 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 63676 KB Output is correct
2 Correct 389 ms 77216 KB Output is correct
3 Correct 425 ms 77532 KB Output is correct
4 Correct 471 ms 82240 KB Output is correct
5 Correct 424 ms 72004 KB Output is correct
6 Correct 351 ms 83448 KB Output is correct
7 Correct 557 ms 73848 KB Output is correct
8 Correct 485 ms 81872 KB Output is correct
9 Correct 406 ms 78016 KB Output is correct
10 Correct 271 ms 86792 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 59844 KB Output is correct
2 Correct 551 ms 52936 KB Output is correct
3 Correct 397 ms 65912 KB Output is correct
4 Correct 430 ms 59116 KB Output is correct
5 Correct 315 ms 75000 KB Output is correct
6 Correct 337 ms 77372 KB Output is correct
7 Correct 340 ms 77304 KB Output is correct
8 Correct 733 ms 67316 KB Output is correct
9 Correct 513 ms 64488 KB Output is correct
10 Correct 250 ms 85880 KB Output is correct