Submission #258175

#	Time	Username	Problem	Language	Result	Execution time	Memory
258175		Sorting	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	560 ms	67392 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e6 + 3;
const int k_Log_N = 20;

int pos[k_N];
int t, cnt;

char c[k_N];
int len[k_N];
int up[k_Log_N][k_N]; 

void Init() {
    t = 0;
    for(int i = 0; i < k_Log_N; ++i)
        up[i][0] = 0;
    
    pos[0] = 0;
    c[0] = '-';
    len[0] = 0;
    cnt = 1;
}

void TypeLetter(char L){
    t++;
    pos[t] = cnt;
    c[cnt] = L;

    len[cnt] = len[pos[t - 1]] + 1;
    up[0][cnt] = pos[t - 1];
    for(int i = 1; i < k_Log_N; ++i)
        up[i][cnt] = up[i - 1][up[i - 1][cnt]];
    cnt++;
}

void UndoCommands(int U){
    pos[t + 1] = pos[t - U];
    t++;
}

char GetLetter(int P){
    int go_back = len[pos[t]] - P - 1;
    if(!go_back) return c[pos[t]];

    int curr = pos[t];
    for(int i = k_Log_N - 1; i >= 0; --i)
        if(go_back & (1 << i))
            curr = up[i][curr];

    return c[curr];
}
/*
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
*/

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