Submission #23616

#	Time	Username	Problem	Language	Result	Execution time	Memory
23616		mohammad_kilani	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	783 ms	142472 KiB

scrivener

//#include"grader.h"
#include<vector>
using namespace std;

int node = 0;
int lastnode = 0;
vector<pair<int,char> > g[1000010];
int dp[23][1000010];
vector<int> curnode;
char chr[1000100];
int depth[1000100];

void Init() {
    dp[0][0] = -1;
    curnode.push_back(0);
    return;
}

void TypeLetter(char L) {
    node++;
    g[lastnode].push_back(make_pair(node,L));
    dp[0][node] = lastnode;
    for(int k=1;k<=22;k++){
        if(dp[k-1][node] == -1)
            dp[k][node] = -1;
        else
            dp[k][node] = dp[k-1][dp[k-1][node]];
    }
    chr[node] = L;
    depth[node] = depth[lastnode] + 1;
    curnode.push_back(node);
    lastnode = node;
}

void UndoCommands(int U) {
    int tmpnode = curnode[curnode.size()-U-1];
    lastnode = tmpnode;
    curnode.push_back(lastnode);
}

char GetLetter(int P) {
    int u = lastnode;
    P++;
    for(int i=22;i>=0;i--){
        if(depth[u]-(1<<i) >= P){
            u = dp[i][u];
        }
    }
    return chr[u];

}

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