Submission #1266588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266588		lambd47	Crayfish scrivener (IOI12_scrivener)	C++20	5 / 100	47 ms	83708 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

const int lg=20;
int at=0;
const int MX=1e6+7;
vector<vector<int>> dp(lg,vector<int> (MX,0));
vector<char> c(MX);
vector<int> prof(MX);

void calc(int aux){
    dp[0][at]=aux;
    L(i,1,lg-1){
        dp[i][at]=dp[i-1][dp[i-1][at]];
    }
}



void Init() {
    prof[0]=-1;
    c[at]='x';
    at++;
}

void TypeLetter(char L) {
    c[at]=L;
    prof[at]=prof[at-1]+1;
    calc(at-1);
    at++;
}

void UndoCommands(int U) {
    auto id=at-U-1;
    c[at]=c[id];
    prof[at]=prof[id];
    dp[at]=dp[id];
    at++;
}

char GetLetter(int P) {
    int id=at-1;
    int d=prof[id]-P;
    L(i,0,lg-1){
        if((1<<i)&d)id=dp[i][id];
    }
    return c[id];
}

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