Submission #437131

#	Time	Username	Problem	Language	Result	Execution time	Memory
437131		aymane7	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	984 ms	130116 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
vector<vector<int>> parent(N,vector<int>(21,0));
vector<char> letter(N);
vector<int> depth(N,0);
int cur=0;
void Init(){
    letter[0]='.';
}
void TypeLetter(char c){
    cur++;
    depth[cur]=depth[cur-1]+1;
    parent[cur][0]=cur-1;
    letter[cur]=c;
    for(int i=1;i<21;i++)
        parent[cur][i]=parent[parent[cur][i-1]][i-1];
}
void UndoCommands(int u){
    int nw=cur+1;
    depth[nw]=depth[cur-u];
    letter[nw]=letter[cur-u];
    for(int i=0;i<21;i++)
        parent[nw][i]=parent[cur-u][i];
    cur++;
}
char GetLetter(int pos){
    pos++;
    //find kth parent of cur st k=depth[cur]-pos
    int k=depth[cur]-pos;
    if(k==0)
        return letter[cur];
    int cp=cur;
    for(int i=20;i>=0;i--)
        if((1<<i)&k)
            cp=parent[cp][i];
    return letter[cp];
}
/*
int main(){
    Init();
    TypeLetter('a');
    TypeLetter('b');
    cout<<GetLetter(1)<<endl;
    TypeLetter('d');
    UndoCommands(2);
    UndoCommands(1);
    cout<<GetLetter(2)<<endl;
    TypeLetter('e');
    UndoCommands(1);
    UndoCommands(5);
    TypeLetter('c');
    cout<<GetLetter(2)<<endl;
    UndoCommands(2);
    cout<<GetLetter(2)<<endl;
}
*/

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