oj.uz

Submission #140871

# Submission time Handle Problem Language Result Execution time Memory
140871 2019-08-05T22:25:28 Z silxikys Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 799 ms 133752 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e6+6, maxk = 20;

struct Node
{
    Node* par[maxk];
    char c;
    int len;
    Node(char cc = '#', Node *p = NULL) {
        c = cc;
        par[0] = p;
        len = p == NULL ? 0 : p->len + 1;
        for (int k = 1; k < maxk; k++) {
            if (par[k-1] == NULL) break;
            par[k] = par[k-1]->par[k-1];
        }
    }
};

string s(Node *test) {
    string s;
    while (test != NULL) {
        s = s + test->c;
        test = test->par[0];
    }
    reverse(s.begin(),s.end());
    return s;
}

Node* nodes[maxn];
int q;

void Init() {
    q = 0;
    nodes[q++] = new Node();
}

void TypeLetter(char L) {
    nodes[q] = new Node(L,nodes[q-1]);
    q++;
    //cout << q << ": " << s(nodes[q-1]) << '\n';
}

void UndoCommands(int U) {
    nodes[q] = nodes[q-U-1];
    q++;
    //cout << q << ": " << s(nodes[q-1]) << '\n';
}

char GetLetter(int P) {
    Node *curr = nodes[q-1];
    P = curr->len - 1 - P;
    for (int k = maxk-1; k >= 0; k--) {
        if (1<<k <= P) {
            P -= 1<<k;
            curr = curr->par[k];
        }
    }
    //cout << s(nodes[q-1]) << '\n';
    return curr->c;
}

/*
int main()
{
    Init();
    TypeLetter('a');
    TypeLetter('b');
    cout << GetLetter(1) << '\n';
    TypeLetter('d');
    UndoCommands(2);
    UndoCommands(1);
    cout << GetLetter(2) << '\n';
    TypeLetter('e');
    UndoCommands(1);
    UndoCommands(5);
    TypeLetter('c');
    cout << GetLetter(2) << '\n';
    UndoCommands(2);
    cout << GetLetter(2) << '\n';
}
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 1016 KB Output is correct
7 Correct 4 ms 1016 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 3 ms 628 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 109496 KB Output is correct
2 Correct 694 ms 121084 KB Output is correct
3 Correct 440 ms 119264 KB Output is correct
4 Correct 419 ms 97144 KB Output is correct
5 Correct 484 ms 104312 KB Output is correct
6 Correct 517 ms 131192 KB Output is correct
7 Correct 468 ms 66780 KB Output is correct
8 Correct 552 ms 98300 KB Output is correct
9 Correct 672 ms 133752 KB Output is correct
10 Correct 254 ms 98828 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 94436 KB Output is correct
2 Correct 799 ms 84396 KB Output is correct
3 Correct 407 ms 92664 KB Output is correct
4 Correct 443 ms 71016 KB Output is correct
5 Correct 520 ms 100600 KB Output is correct
6 Correct 520 ms 94928 KB Output is correct
7 Correct 555 ms 101184 KB Output is correct
8 Correct 609 ms 50920 KB Output is correct
9 Correct 717 ms 87108 KB Output is correct
10 Correct 269 ms 98032 KB Output is correct