제출 #106337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106337		Lawliet	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	12 / 100	723 ms	66040 KiB

scrivener

#include <bits/stdc++.h>

#define LOG 22
#define MAX 1000010

using namespace std;

class pilha
{
	public:
		
		void add(char s)
		{
			curInd++;
			curNode++;
			
			v[curNode] = s;
			version[curInd] = curNode;
			dp[curNode][0] = version[curInd - 1];
			prof[curNode] = prof[dp[curNode][0]] + 1;
			
			for(int k = 1 ; k < LOG ; k++)
				dp[curNode][k]= dp[dp[curNode][k - 1]][k - 1];
		}
		
		void back(int k)
		{
			curInd++;
			
			version[curInd] = version[curInd - k - 1];
		}
		
		char query(int k)
		{
			int d = prof[curNode] - k;
			int cur = curNode;
			
			for(int g = 0 ; g < LOG ; g++)
				if(d & (1 << g))
					cur = dp[cur][g];
					
			return v[cur];
		}
		
	private:
		
		int curInd;
		int curNode;
		
		int prof[MAX];
		int dp[MAX][LOG];
		int version[MAX];
		
		char v[MAX];
};

pilha p;

void Init() { }

void TypeLetter(char L) { p.add( L ); }

void UndoCommands(int U) { p.back( U ); }

char GetLetter(int P) { return p.query( P + 1 ); }

/*int q;
int n1, n2;

int main()
{
	scanf("%d",&q);
	
	Init();
	
	for(int g = 0 ; g < q ; g++)
	{
		scanf("%d %d",&n1,&n2);
		
		if(n1 == 1) TypeLetter(n2 + 'a');
		if(n1 == 2) UndoCommands(n2);
		if(n1 == 3) printf("%c\n",GetLetter(n2));
	}
}*/

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