oj.uz

Submission #64432

# Submission time Handle Problem Language Result Execution time Memory
64432 2018-08-04T12:58:29 Z zubec Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
 1000 ms 132376 KB 
//#include "grader.h"
#include <bits/stdc++.h>
char last;

struct node{
    char c;

    node *pr[23];
    int deep;
    node(){
        for (int i = 0; i <= 21; i++)
            pr[i] = nullptr;
        deep = 0;
    }
};

node* bor[1000100];

int cnt;

void Init(){
    cnt = 0;
    bor[0] = new node();
}


void TypeLetter(char L) {
    ++cnt;
    if (!bor[cnt])
        bor[cnt] = new node();
    bor[cnt]->c = L;
    bor[cnt]->pr[0] = bor[cnt-1];
    for (int i = 1; i <= 21; i++){
        bor[cnt]->pr[i] = (bor[cnt]->pr[i - 1] ? bor[cnt]->pr[i - 1]->pr[i - 1] : nullptr);
    }
    bor[cnt]->deep = bor[cnt-1]->deep+1;
}

void UndoCommands(int U) {
    ++cnt;
    bor[cnt] = bor[cnt-U-1];
}

char GetLetter(int P) {
    node* ver = bor[cnt];
    int h = ver->deep-P-1;
    for (int i = 21; i >= 0; i--){
        if (h - (1<<i) >= 0){
            h -= (1<<i);
            ver = ver->pr[i];
        }
    }
    return ver->c;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 420 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 508 KB Output is correct
7 Correct 2 ms 528 KB Output is correct
8 Correct 3 ms 548 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 3 ms 576 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 584 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 712 KB Output is correct
5 Correct 2 ms 712 KB Output is correct
6 Correct 2 ms 712 KB Output is correct
7 Correct 2 ms 712 KB Output is correct
8 Correct 3 ms 712 KB Output is correct
9 Correct 3 ms 712 KB Output is correct
10 Correct 3 ms 712 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 892 KB Output is correct
2 Correct 7 ms 908 KB Output is correct
3 Correct 4 ms 1052 KB Output is correct
4 Correct 5 ms 1336 KB Output is correct
5 Correct 4 ms 1336 KB Output is correct
6 Correct 7 ms 1536 KB Output is correct
7 Correct 5 ms 1640 KB Output is correct
8 Correct 5 ms 1640 KB Output is correct
9 Correct 5 ms 1640 KB Output is correct
10 Correct 4 ms 1640 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 128100 KB Output is correct
2 Execution timed out 1070 ms 132376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

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