oj.uz

Submission #414136

# Submission time Handle Problem Language Result Execution time Memory
414136 2021-05-30T06:36:24 Z blue Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 968 ms 86660 KB 
#include <vector>
#include <iostream>
using namespace std;

int curr;
int len[1000001];
char last[1000001];
int letter_anc[1000001][20];

void Init()
{
    curr = 0;

    len[0] = -1;
    last[0] = '?';
    for(int e = 0; e < 20; e++)
        letter_anc[0][e] = 0;
}

void TypeLetter(char L)
{
    curr++;
    len[curr] = len[curr-1] + 1;
    last[curr] = L;

    letter_anc[curr][0] = curr-1;
    for(int e = 1; e < 20; e++)
    {
        letter_anc[curr][e] = letter_anc[ letter_anc[curr][e-1] ][e-1];
    }

    // cerr << curr << '\n';
}

void UndoCommands(int U)
{
    int prev = curr - U;

    // cerr << "making copy of " << prev << '\n';

    curr++;
    len[curr] = len[prev];
    last[curr] = last[prev];

    letter_anc[curr][0] = letter_anc[prev][0];

    for(int e = 1; e < 20; e++)
    {
        letter_anc[curr][e] = letter_anc[ letter_anc[curr][e-1] ][e-1];
    }

    // cerr << curr << '\n';
}

char GetLetter(int P)
{
    int pos = curr;
    for(int e = 19; e >= 0; e--)
        if(len[ letter_anc[pos][e] ] >= P)
            pos = letter_anc[pos][e];

    return last[pos];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 60728 KB Output is correct
2 Correct 481 ms 73540 KB Output is correct
3 Correct 410 ms 73300 KB Output is correct
4 Correct 484 ms 76776 KB Output is correct
5 Correct 533 ms 67868 KB Output is correct
6 Correct 418 ms 79972 KB Output is correct
7 Correct 873 ms 68588 KB Output is correct
8 Correct 800 ms 81592 KB Output is correct
9 Correct 501 ms 77812 KB Output is correct
10 Correct 331 ms 86660 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 55704 KB Output is correct
2 Correct 654 ms 48140 KB Output is correct
3 Correct 465 ms 60996 KB Output is correct
4 Correct 511 ms 53232 KB Output is correct
5 Correct 486 ms 70940 KB Output is correct
6 Correct 511 ms 73328 KB Output is correct
7 Correct 522 ms 73216 KB Output is correct
8 Correct 968 ms 62148 KB Output is correct
9 Correct 941 ms 64152 KB Output is correct
10 Correct 335 ms 85596 KB Output is correct