제출 #512644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
512644		AdamGS	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1055 ms	153268 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7, LG=20;
int ile[LIM], nxt[LIM][LG], sum[LIM][LG], akt;
char V[LIM];
void licz() {
	for(int i=1; i<LG; ++i) {
		nxt[akt][i]=nxt[nxt[akt][i-1]][i-1];
		sum[akt][i]=sum[akt][i-1]+sum[nxt[akt][i-1]][i-1];
	}
}
void Init() {}
void TypeLetter(char x) {
	++akt;
	V[akt]=x;
	ile[akt]=ile[akt-1]+1;
	nxt[akt][0]=akt-1;
	sum[akt][0]=1;
	licz();
}
void UndoCommands(int x) {
	++akt;
	ile[akt]=ile[akt-x-1];
	nxt[akt][0]=akt-x-1;
	licz();
}
char GetLetter(int x) {
	x=ile[akt]-x-1;
	int p=akt;
	for(int i=LG-1; i>=0; --i) if(sum[p][i]<=x) {
		x-=sum[p][i];
		p=nxt[p][i];
	}
	return V[p];
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40