oj.uz

Submission #252544

# Submission time Handle Problem Language Result Execution time Memory
252544 2020-07-25T20:14:53 Z Kubin Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 842 ms 133496 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr size_t MAX = 1 << 20, MAX_LOG = __lg(MAX);

struct node
{
    char ch;
    node* ptr[MAX_LOG];
} epsilon;

size_t length(node* curr)
{
    if(curr == &epsilon)
        return 0;

    size_t r = 0;
    for(size_t k = MAX_LOG; k --> 0; )
        if(curr->ptr[k] != &epsilon)
            curr = curr->ptr[k], r += 1 << k;
    return r + 1;
}

vector<node*> history;

void Init()
{
    history.reserve(MAX);

    epsilon.ch = 0;
    fill(begin(epsilon.ptr), end(epsilon.ptr), &epsilon);
    history.push_back(&epsilon);
}

void TypeLetter(char c)
{
    node* next = new node;
    next->ch = c;
    next->ptr[0] = history.back();
    for(size_t k = 1; k < MAX_LOG; k++)
        next->ptr[k] = (next->ptr[k-1])->ptr[k-1];
    history.push_back(next);
}

void UndoCommands(int i)
{
    history.push_back(history.rbegin()[i]);
}

char GetLetter(int i)
{
    node* curr = history.back();

    i = length(curr) - i - 1;
    for(size_t k = MAX_LOG; k --> 0; )
        if(i >> k & 1)
            curr = curr->ptr[k];

    return curr->ch;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 380 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 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 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 0 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 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 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 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 109524 KB Output is correct
2 Correct 521 ms 120952 KB Output is correct
3 Correct 477 ms 119288 KB Output is correct
4 Correct 452 ms 97112 KB Output is correct
5 Correct 474 ms 104184 KB Output is correct
6 Correct 522 ms 131008 KB Output is correct
7 Correct 510 ms 66680 KB Output is correct
8 Correct 525 ms 98296 KB Output is correct
9 Correct 570 ms 133496 KB Output is correct
10 Correct 297 ms 98808 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 94512 KB Output is correct
2 Correct 842 ms 84088 KB Output is correct
3 Correct 431 ms 92664 KB Output is correct
4 Correct 464 ms 70776 KB Output is correct
5 Correct 478 ms 100476 KB Output is correct
6 Correct 502 ms 94840 KB Output is correct
7 Correct 456 ms 100856 KB Output is correct
8 Correct 563 ms 51068 KB Output is correct
9 Correct 716 ms 87160 KB Output is correct
10 Correct 281 ms 97916 KB Output is correct