답안 #286604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286604	2020-08-30T15:20:27 Z	amiratou	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	100 / 100	992 ms	128040 KB

scrivener

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int LOG=20,MX=(int)(1e6+1);

int up[MX][LOG],d[MX],idx;
char car[MX];
vector<int> vec[MX];
 
void Init() {
 
}
 
void TypeLetter(char L) {
	vec[idx].pb(idx+1);
	d[idx+1]=d[idx]+1;
	up[idx+1][0]=idx;
	for (int i = 1; i < LOG; ++i)
		up[idx+1][i]=up[up[idx+1][i-1]][i-1];
	car[idx+1]=L;
	idx++;
}
 
void UndoCommands(int U) {
	d[idx+1]=d[idx-U];
	up[idx+1][0]=up[idx-U][0];
	for (int i = 1; i < LOG; ++i)
		up[idx+1][i]=up[up[idx+1][i-1]][i-1];
	if(idx!=U){
		vec[up[idx-U][0]].pb(idx+1);
		car[idx+1]=car[idx-U];
	}
	idx++;
}
 
char GetLetter(int P) {
	int k=d[idx]-1-P,a=idx;
	for (int i = 0; i < LOG; ++i)
		if((k>>i)&1)a=up[a][i];
	return car[a];
 
}

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

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

Subtask #3

22.0 / 22.0

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

Subtask #4

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	467 ms	101632 KB	Output is correct
2	Correct	588 ms	116600 KB	Output is correct
3	Correct	576 ms	115804 KB	Output is correct
4	Correct	698 ms	115816 KB	Output is correct
5	Correct	505 ms	107384 KB	Output is correct
6	Correct	447 ms	124408 KB	Output is correct
7	Correct	992 ms	102136 KB	Output is correct
8	Correct	956 ms	121336 KB	Output is correct
9	Correct	581 ms	123768 KB	Output is correct
10	Correct	376 ms	128040 KB	Output is correct

Subtask #5

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	559 ms	93816 KB	Output is correct
2	Correct	585 ms	84472 KB	Output is correct
3	Correct	559 ms	99064 KB	Output is correct
4	Correct	582 ms	87288 KB	Output is correct
5	Correct	485 ms	109944 KB	Output is correct
6	Correct	514 ms	111608 KB	Output is correct
7	Correct	485 ms	112376 KB	Output is correct
8	Correct	987 ms	92920 KB	Output is correct
9	Correct	823 ms	96120 KB	Output is correct
10	Correct	372 ms	123000 KB	Output is correct