Submission #255670

#	Time	Username	Problem	Language	Result	Execution time	Memory
255670		Akashi	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1100 ms	130596 KiB

scrivener

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

const int DIM = 1e6 + 5;

pair <int, int> cur = {0, 0};

vector <vector <int>> tt;
vector <vector <int>> pref;

int nr1, nr2;

char ch[DIM];
int le[DIM], le2[DIM], tang[DIM];
int p2[25];
void Init() {
    tt.emplace_back(); pref.emplace_back();
    p2[0] = 1;
    for (int i = 1; i <= 20 ; ++i)
        p2[i] = p2[i - 1] * 2;
}

void TypeLetter(char L) {
    ++nr1; ++nr2;

    le[nr1] = le[cur.first] + 1;
    ch[nr1] = L;

    pref.emplace_back();

    pref[nr1].push_back(cur.first);
    for (int k = 1; p2[k] < le[nr1] ; ++k)
        pref[nr1].push_back(pref[pref[nr1][k - 1]][k - 1]);

    le2[nr2] = le2[cur.second] + 1;

    tt.emplace_back();

    tt[nr2].push_back(cur.second);
    for (int k = 1; p2[k] < le2[nr2] ; ++k)
        tt[nr2].push_back(tt[tt[nr2][k - 1]][k - 1]);

    cur = {nr1, nr2};
    tang[nr2] = nr1;
}

void UndoCommands(int U) {
    ++nr2;

    pair <int, int> aux = cur;
    for (int k = 0; U > 0 ; ++k) {
        if (p2[k] & U) {
            cur.second = tt[cur.second][k];
            U = U ^ p2[k];
        }
    }

    cur = {tang[cur.second], nr2};
    tang[nr2] = cur.first;

    le2[cur.second] = le2[aux.second] + 1;

    tt.emplace_back();

    tt[cur.second].push_back(aux.second);
    for (int k = 1; p2[k] < le2[cur.second] ; ++k)
        tt[cur.second].push_back(tt[tt[cur.second][k - 1]][k - 1]);
}

char GetLetter(int P) {
    ++P;

    int dif = le[cur.first] - P;
    int ind = cur.first;

    for (int k = 0; dif > 0 ; ++k) {
        if (p2[k] & dif) {
            ind = pref[ind][k];
            dif = dif ^ p2[k];
        }
    }

    return ch[ind];
}

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