oj.uz

답안 #119248

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119248 2019-06-20T18:19:22 Z ioilolcom 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 624 ms 75760 KB 
#include <vector>
using namespace std;

int node = 0;
int lastnode = 0;
//vector<pair<int,char> > g[1000010];
int dp[23][1000010];
vector<int> curnode;
char chr[1000100];
int depth[1000100];

void Init() {
	dp[0][0] = -1;
	curnode.push_back(0);
	return;
}

void TypeLetter(char L) {
	node++;
	//g[lastnode].push_back(make_pair(node,L));
	dp[0][node] = lastnode;
	for(int k=1; k<=22; k++) {
		if(dp[k-1][node] == -1)
			dp[k][node] = -1;
		else
			dp[k][node] = dp[k-1][dp[k-1][node]];
	}
	chr[node] = L;
	depth[node] = depth[lastnode] + 1;
	curnode.push_back(node);
	lastnode = node;
}

void UndoCommands(int U) {
	int tmpnode = curnode[curnode.size()-U-1];
	lastnode = tmpnode;
	curnode.push_back(lastnode);
}

char GetLetter(int P) {
	int u = lastnode;
	P++;
	for(int i=22; i>=0; i--) {
		if(depth[u]-(1<<i) >= P) {
			u = dp[i][u];
		}
	}
	return chr[u];

}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 768 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 59400 KB Output is correct
2 Correct 393 ms 68784 KB Output is correct
3 Correct 339 ms 68064 KB Output is correct
4 Correct 350 ms 56420 KB Output is correct
5 Correct 413 ms 59872 KB Output is correct
6 Correct 324 ms 74184 KB Output is correct
7 Correct 362 ms 39656 KB Output is correct
8 Correct 330 ms 56652 KB Output is correct
9 Correct 432 ms 75760 KB Output is correct
10 Correct 220 ms 56364 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 546 ms 50496 KB Output is correct
2 Correct 624 ms 49420 KB Output is correct
3 Correct 362 ms 53828 KB Output is correct
4 Correct 373 ms 42592 KB Output is correct
5 Correct 311 ms 57824 KB Output is correct
6 Correct 312 ms 54528 KB Output is correct
7 Correct 331 ms 57824 KB Output is correct
8 Correct 479 ms 31260 KB Output is correct
9 Correct 566 ms 50916 KB Output is correct
10 Correct 227 ms 55904 KB Output is correct