Submission #49531

#	Time	Username	Problem	Language	Result	Execution time	Memory
49531		ho94949	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	923 ms	179004 KiB

scrivener

const int lgMAXN = 20;
const int MAXN = 1 << 20;
int len;
int arr[MAXN];
int sparse[MAXN][lgMAXN];


void Init() {
    len = 0;
}

void TypeLetter(char L) {
    arr[++len] = L;
    sparse[len][0] = len;
    for(int i=1; i<lgMAXN; ++i)
        if(sparse[len][i-1] == 0) sparse[len][i] = 0;
        else sparse[len][i] = sparse[sparse[len][i-1]-1][i-1];
}

void UndoCommands(int U) {
    arr[++len] = -U;
    for(int i=0; i<lgMAXN; ++i)
        sparse[len][i] = sparse[len-U-1][i];
}

char GetLetter(int P) {
    
    int c = 0, idx = len;
    for(int i=lgMAXN-1; i>=0; --i)
        if(sparse[idx][i])
        {
            c += (1<<i);
            idx = sparse[idx][i]-1;
        }

    int ans = len;
    for(int i=lgMAXN-1; i>=0; --i)
        if((c-P)&(1<<i))
            ans = sparse[ans][i]-1;
    
    return arr[ans+1];
}

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