oj.uz

답안 #104263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104263 2019-04-04T14:10:15 Z arman_ferdous 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 983 ms 89108 KB 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
char c[N];
int lev[N];
int cur, freePtr;
int p[N][20], state[N], ptr;

void Init() {
	lev[0] = -1;
	memset(p,-1,sizeof p);
	c[0] = '?';
	cur = 0; freePtr = 1;
	state[0] = cur; ptr = 0;
}

void TypeLetter(char L) {
	int idx = freePtr++;
	p[idx][0] = cur;
	c[idx] = L, lev[idx] = lev[cur] + 1;
	cur = idx;

	for(int j = 1; j < 20; ++j)
		if(p[cur][j-1] + 1)
			p[cur][j] = p[p[cur][j-1]][j-1];
	state[++ptr] = cur;
}

void UndoCommands(int U) {
	state[ptr+1] = state[max(0, ptr - U)];
	ptr++;
	cur = state[ptr];
}

char GetLetter(int P) {
	int tmp = cur, need = lev[cur] - P;
	for(int j = 19; j >= 0; --j)
		if(need >= (1<<j)) {
			need -= (1<<j);
			tmp = p[tmp][j];
		}
	return c[tmp];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 78584 KB Output is correct
2 Correct 69 ms 78712 KB Output is correct
3 Correct 68 ms 78560 KB Output is correct
4 Correct 68 ms 78584 KB Output is correct
5 Correct 69 ms 78584 KB Output is correct
6 Correct 69 ms 78584 KB Output is correct
7 Correct 65 ms 78584 KB Output is correct
8 Correct 65 ms 78584 KB Output is correct
9 Correct 66 ms 78556 KB Output is correct
10 Correct 66 ms 78584 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 78596 KB Output is correct
2 Correct 69 ms 78568 KB Output is correct
3 Correct 68 ms 78584 KB Output is correct
4 Correct 69 ms 78712 KB Output is correct
5 Correct 68 ms 78664 KB Output is correct
6 Correct 78 ms 78668 KB Output is correct
7 Correct 71 ms 78584 KB Output is correct
8 Correct 67 ms 78584 KB Output is correct
9 Correct 73 ms 78584 KB Output is correct
10 Correct 71 ms 78584 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 78712 KB Output is correct
2 Correct 76 ms 78640 KB Output is correct
3 Correct 67 ms 78712 KB Output is correct
4 Correct 72 ms 78524 KB Output is correct
5 Correct 66 ms 78716 KB Output is correct
6 Correct 66 ms 78712 KB Output is correct
7 Correct 70 ms 78712 KB Output is correct
8 Correct 66 ms 78712 KB Output is correct
9 Correct 66 ms 78712 KB Output is correct
10 Correct 71 ms 78712 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 774 ms 85216 KB Output is correct
2 Correct 800 ms 86008 KB Output is correct
3 Correct 464 ms 85752 KB Output is correct
4 Correct 503 ms 85472 KB Output is correct
5 Correct 703 ms 85464 KB Output is correct
6 Correct 505 ms 86520 KB Output is correct
7 Correct 570 ms 84408 KB Output is correct
8 Correct 604 ms 85400 KB Output is correct
9 Correct 775 ms 86468 KB Output is correct
10 Correct 298 ms 85640 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 909 ms 84708 KB Output is correct
2 Correct 933 ms 84216 KB Output is correct
3 Correct 523 ms 84832 KB Output is correct
4 Correct 493 ms 84220 KB Output is correct
5 Correct 517 ms 85368 KB Output is correct
6 Correct 533 ms 85324 KB Output is correct
7 Correct 545 ms 85356 KB Output is correct
8 Correct 809 ms 83704 KB Output is correct
9 Correct 983 ms 84596 KB Output is correct
10 Correct 279 ms 89108 KB Output is correct