oj.uz

Submission #550650

# Submission time Handle Problem Language Result Execution time Memory
550650 2022-04-18T18:40:23 Z David_M Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 436 ms 86724 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int curr, last=-1, h[1000006], pa[20][1000006];
char C[1000006];

void add(int x, char c){

    last++;
    pa[0][last]=curr;
    h[last]=h[curr]+1;
    curr=last;
    C[curr]=c;
    for (int i=1; i<20; i++){
        pa[i][curr]=pa[i-1][pa[i-1][curr]];
    }

}

void roll_back(int t){
    curr=++last;
    h[curr]=h[t];
    C[curr]=C[t];
    for (int i=0; i<20; i++){
        pa[i][curr]=pa[i][t];
    }
}

int Kth_parent(int k){
    int Pa=curr;
    for (int i=19; i>=0; i--){
        if(k&(1<<i))Pa=pa[i][Pa];
    }
    return C[Pa];
}

void Init() { h[0]=-1; }

string s;

void TypeLetter(char L) { add(curr, L); }
void UndoCommands(int U) { roll_back(last-U); }
char GetLetter(int P) { return Kth_parent(h[curr]-P); }

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 852 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 63704 KB Output is correct
2 Correct 261 ms 77056 KB Output is correct
3 Correct 280 ms 77292 KB Output is correct
4 Correct 356 ms 82220 KB Output is correct
5 Correct 264 ms 71864 KB Output is correct
6 Correct 213 ms 83456 KB Output is correct
7 Correct 352 ms 73636 KB Output is correct
8 Correct 308 ms 81680 KB Output is correct
9 Correct 271 ms 77920 KB Output is correct
10 Correct 185 ms 86724 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 59520 KB Output is correct
2 Correct 397 ms 52792 KB Output is correct
3 Correct 296 ms 65888 KB Output is correct
4 Correct 325 ms 59032 KB Output is correct
5 Correct 224 ms 74944 KB Output is correct
6 Correct 235 ms 77236 KB Output is correct
7 Correct 239 ms 77132 KB Output is correct
8 Correct 436 ms 66892 KB Output is correct
9 Correct 404 ms 64344 KB Output is correct
10 Correct 189 ms 85772 KB Output is correct