제출 #70929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70929		FLDutchman	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	100 / 100	910 ms	99476 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

char nodes[1000100]; int sz[1000100];
int lift[1000100][21];
int numVersions = 0;

int insert(int l, char c){
    int ver = numVersions++;
    nodes[ver] = c;
    sz[ver] = sz[l]+1;
    //cerr<<getsz(l) << " " << l->lift.size() << endl;
    int i = 0;
    while(true){
        //cout<<getsz(l)<<endl;
        lift[ver][i] = l;
        //cout<<nl->lift.size()<<endl;
        if(lift[l][i] == -1) return ver;
        l = lift[l][i++];
    }    
}

char getletter(int l, int i){
    //cerr<<getsz(l) << " " << l->lift.size() << endl;
    FOR(k, 0, 21) if(i & (1<<k)) l = lift[l][k]; 
    return nodes[l];
}


void Init() {
    sz[0] = nodes[0] = 0;
    numVersions = 1; 
    FOR(i, 0, 1000100) FOR(j, 0, 21) lift[i][j] = -1;
}

void TypeLetter(char L) {
    //for(auto l : v) cout << getsz(l) << " " << (l ?  to_string(l->lift.size()) :"") << endl;
    insert(numVersions-1, L);
}

void UndoCommands(int U) {
    int o = numVersions - 1 - U, n = numVersions++;
    nodes[n] = nodes[o];
    sz[n] = sz[o];
    FOR(i, 0, 21) lift[n][i] = lift[o][i];
}

char GetLetter(int P) {
    int v = numVersions - 1;
    return getletter(v, sz[v]-1 - P);
}

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