oj.uz

Submission #15631

# Submission time Handle Problem Language Result Execution time Memory
15631 2015-07-13T12:38:50 Z progressive Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 559 ms 109580 KB 
using namespace std;
static const int MAXN=1010101;
static bool isundo[MAXN];
static int real[MAXN];
static char working[MAXN];
static int length[MAXN];
static int sparse[MAXN][25];
static int turn;
void Init()
{
	turn=1;
	real[0]=0;
	length[0]=0;
	for(int i=0;i<25;i++) sparse[0][i]=-1;
}

void TypeLetter(char L)
{
	isundo[turn]=false;
	working[turn]=L;
	length[turn]=length[turn-1]+1;
	real[turn]=turn;
	sparse[turn][0]=real[turn-1];
	for(int i=1;i<25;i++)
	{
		int v=sparse[turn][i-1];
		if(v==-1) sparse[turn][i]=-1;
		else sparse[turn][i]=sparse[v][i-1];
	}
	turn++;
	return;
}

void UndoCommands(int U)
{
	isundo[turn]=true;
	real[turn]=real[turn-U-1];
	length[turn]=length[turn-U-1];
	turn++;
	return;
}
char GetLetter(int P)
{
	int nowturn=turn-1;
	nowturn=real[nowturn];
	//printf("%d\n ",nowturn);
	int spb=length[nowturn]-P-1;
	
	int i=24;
	while(spb>0)
	{
		for(;;i--)
		{
			if(spb>=(1<<i))
			{
				spb-=1<<i;
				nowturn=sparse[nowturn][i];
				break;
			}
		}
	}
	return working[nowturn];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 109580 KB Output is correct
2 Correct 423 ms 109580 KB Output is correct
3 Correct 315 ms 109580 KB Output is correct
4 Correct 307 ms 109580 KB Output is correct
5 Correct 380 ms 109580 KB Output is correct
6 Correct 398 ms 109580 KB Output is correct
7 Correct 392 ms 109580 KB Output is correct
8 Correct 416 ms 109580 KB Output is correct
9 Correct 468 ms 109580 KB Output is correct
10 Correct 229 ms 109580 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 109580 KB Output is correct
2 Correct 467 ms 109580 KB Output is correct
3 Correct 312 ms 109580 KB Output is correct
4 Correct 325 ms 109580 KB Output is correct
5 Correct 362 ms 109580 KB Output is correct
6 Correct 351 ms 109580 KB Output is correct
7 Correct 364 ms 109580 KB Output is correct
8 Correct 442 ms 109580 KB Output is correct
9 Correct 559 ms 109580 KB Output is correct
10 Correct 218 ms 109580 KB Output is correct