oj.uz

Submission #255645

# Submission time Handle Problem Language Result Execution time Memory
255645 2020-08-01T13:23:43 Z Akashi Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
 1000 ms 163200 KB 
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e6 + 5;

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

vector <vector <pair <int, int>>> tt;
vector <vector <int>> pref;

int nr1, nr2;

char ch[DIM];
int le[DIM], le2[DIM];

void Init() {tt.emplace_back(); pref.emplace_back();}

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; (1 << 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);
    for (int k = 1; (1 << k) < le2[nr2] ; ++k)
        tt[nr2].push_back(tt[tt[nr2][k - 1].second][k - 1]);

    cur = {nr1, nr2};
}

void UndoCommands(int U) {
    ++nr2;

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

    cur = {cur.first, nr2};

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

    tt.emplace_back();

    tt[cur.second].push_back(aux);
    for (int k = 1; (1 << k) < le2[cur.second] ; ++k)
        tt[cur.second].push_back(tt[tt[cur.second][k - 1].second][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 ((1 << k) & dif) {
            ind = pref[ind][k];
            dif = dif - (1 << k);
        }
    }

    return ch[ind];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 4 ms 1408 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 5 ms 1536 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1408 KB Output is correct
9 Correct 4 ms 1408 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 163200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 152588 KB Time limit exceeded
2 Halted 0 ms 0 KB -