oj.uz

Submission #486321

# Submission time Handle Problem Language Result Execution time Memory
486321 2021-11-11T08:51:17 Z alextodoran Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 565 ms 133508 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int BITS = 20;

struct Node
{
    int length;
    char parentLetter;
    Node* ancestor[BITS];

    Node (char letter = '-')
    {
        length = 0;
        parentLetter = letter;
        for(int bit = 0; bit < BITS; bit++)
            ancestor[bit] = this;
    }
};

Node* root = new Node();

void Init ()
{
    ;
}

vector <Node*> nodes = {root};

void TypeLetter (char letter)
{
    Node* son = new Node(letter);
    son->ancestor[0] = nodes.back();
    son->length = son->ancestor[0]->length + 1;
    for(int bit = 1; bit < BITS; bit++)
    {
        if(son->ancestor[bit - 1] == root)
            son->ancestor[bit] = root;
        else
            son->ancestor[bit] = son->ancestor[bit - 1]->ancestor[bit - 1];
    }
    nodes.push_back(son);
}

void UndoCommands (int cnt)
{
    nodes.push_back(nodes.end()[- (1 + cnt)]);
}

char GetLetter (int pos)
{
    Node* node = nodes.back();
    for(int bit = BITS - 1; bit >= 0; bit--)
        if(node->length - (1 << bit) > pos)
            node = node->ancestor[bit];
    return node->parentLetter;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 109360 KB Output is correct
2 Correct 420 ms 120768 KB Output is correct
3 Correct 335 ms 119200 KB Output is correct
4 Correct 296 ms 96984 KB Output is correct
5 Correct 404 ms 104176 KB Output is correct
6 Correct 407 ms 130856 KB Output is correct
7 Correct 346 ms 66588 KB Output is correct
8 Correct 378 ms 98088 KB Output is correct
9 Correct 487 ms 133508 KB Output is correct
10 Correct 223 ms 98640 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 94420 KB Output is correct
2 Correct 565 ms 83956 KB Output is correct
3 Correct 325 ms 92424 KB Output is correct
4 Correct 313 ms 70724 KB Output is correct
5 Correct 365 ms 100512 KB Output is correct
6 Correct 342 ms 94712 KB Output is correct
7 Correct 396 ms 100868 KB Output is correct
8 Correct 466 ms 50892 KB Output is correct
9 Correct 550 ms 86936 KB Output is correct
10 Correct 217 ms 97820 KB Output is correct