Submission #868524

#	Time	Username	Problem	Language	Result	Execution time	Memory
868524		HuyQuang_re_Zero	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	700 ms	144664 KiB

scrivener

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define mxn 1000005
using namespace std;

struct International_Olympiad_in_Informatics
{
    struct trie
    {
        trie *p[21];
        char up;
        int h=0;
    } *r,*node[mxn];

    int n;
    void Init() { r=new trie(); node[0]=r; }
    void add(char ch)
    {
        n++;
        trie *u=new trie(); node[n]=u;
        u->up=ch;
        u->p[0]=node[n-1]; u->h=node[n-1]->h+1;
        for(int i=1;(1<<i)<=u->h;i++)
            u->p[i]=u->p[i-1]->p[i-1];
    }
    void undo(int x)
    {
        n++; node[n]=node[n-1-x];
    }
    char get(int pos)
    {
        trie *u=node[n];
        for(int i=Log(u->h);i>=0;i--)
            if(u->p[i]!=NULL && u->p[i]->h>=pos)
            {
                u=u->p[i];
            }
        return u->up;
    }
} IOI;


void Init() { IOI.Init(); }
void TypeLetter(char L) { IOI.add(L); }
void UndoCommands(int U) { IOI.undo(U); }
char GetLetter(int P) { return IOI.get(P+1); }
/*
int n,k;
char ch,type;
int main()
{
    freopen("scrivener.inp","r",stdin);
    freopen("scrivener.out","w",stdout);
    Init();
    cin>>n;
    while(n--)
    {
        cin>>type;
        if(type=='T') cin>>ch,TypeLetter(ch);
        else if(type=='U') cin>>k,UndoCommands(k);
        else cin>>k,cout<<GetLetter(k)<<'\n';

    }
}*/

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