Submission #1032099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032099		idas	Crayfish scrivener (IOI12_scrivener)	C++11	0 / 100	155 ms	54872 KiB

scrivener

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)

using namespace std;

const int MxN=1e6+1, L=21;
int bin[MxN][L], con[MxN], dp[MxN], cur, com_id, tree_id;
char val[MxN];

void build(int id)
{
    FOR(i, 1, L) bin[id][i]=bin[bin[id][i-1]][i-1];
}

int lift(int id, int d)
{
    FOR(i, 0, L) if(d&(1<<i))
    {
        id=bin[id][i];
    }
    return id;
}

void Init() {}

void TypeLetter(char l) {
    int node=con[cur]; if(cur==0){ node=tree_id+1; dp[node]=0; }
    bin[++tree_id][0]=node;
    con[++com_id]=tree_id;
    dp[tree_id]=dp[node]+1;
    val[tree_id]=l;
    build(tree_id);
}

void UndoCommands(int u) {
    assert(com_id-u>=1);
    con[com_id+1]=con[com_id-u];
    com_id++;
}

char GetLetter(int p) {
    int node=lift(con[com_id], dp[con[com_id]]-p);
//    cout << "Answer node: " << node << '\n';
    return val[node];
}

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