제출 #538423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538423		groshi	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	100 / 100	555 ms	209676 KiB

scrivener

#include<iostream>
#include<string>
using namespace std;
int gdzie=1;
struct wi{
    int dokad[30];
    int skok[21];
    int wys=0;
}*w;
int nowy=2;
int gdzie_w_czasie[1000100];
char litera[1000100];
void dodaj_pot(int ustal)
{
    for(int i=1;i<=20;i++)
        w[ustal].skok[i]=w[w[ustal].skok[i-1]].skok[i-1];
}
int czas=1;
void Init()
{
    w=new wi[1000003];
}
void TypeLetter(char dodaj)
{
    if(w[gdzie].dokad[dodaj-'a']==0)
    {
        litera[nowy]=dodaj;
        w[gdzie].dokad[dodaj-'a']=nowy;
        w[nowy].skok[0]=gdzie;
        w[nowy].wys=w[gdzie].wys+1;
        dodaj_pot(nowy);
        gdzie=nowy;
        nowy++;
    }
    else gdzie=w[gdzie].dokad[dodaj-'a'];
    gdzie_w_czasie[czas]=gdzie;
    czas++;
}
void UndoCommands(int cof)
{
    gdzie=gdzie_w_czasie[czas-cof-1];
    gdzie_w_czasie[czas]=gdzie;
    czas++;
}
char GetLetter(int ile)
{
    int pot=0;
    int gora=gdzie;
    ile=w[gdzie].wys-ile-1;
    while(ile>0)
    {
        if(ile%2==1)
            gora=w[gora].skok[pot];
        ile/=2;
        pot++;
    }
    return litera[gora];
}

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