oj.uz

Submission #70929

# Submission time Handle Problem Language Result Execution time Memory
70929 2018-08-23T17:47:58 Z FLDutchman Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 910 ms 99476 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

char nodes[1000100]; int sz[1000100];
int lift[1000100][21];
int numVersions = 0;

int insert(int l, char c){
    int ver = numVersions++;
    nodes[ver] = c;
    sz[ver] = sz[l]+1;
    //cerr<<getsz(l) << " " << l->lift.size() << endl;
    int i = 0;
    while(true){
        //cout<<getsz(l)<<endl;
        lift[ver][i] = l;
        //cout<<nl->lift.size()<<endl;
        if(lift[l][i] == -1) return ver;
        l = lift[l][i++];
    }    
}

char getletter(int l, int i){
    //cerr<<getsz(l) << " " << l->lift.size() << endl;
    FOR(k, 0, 21) if(i & (1<<k)) l = lift[l][k]; 
    return nodes[l];
}


void Init() {
    sz[0] = nodes[0] = 0;
    numVersions = 1; 
    FOR(i, 0, 1000100) FOR(j, 0, 21) lift[i][j] = -1;
}

void TypeLetter(char L) {
    //for(auto l : v) cout << getsz(l) << " " << (l ?  to_string(l->lift.size()) :"") << endl;
    insert(numVersions-1, L);
}

void UndoCommands(int U) {
    int o = numVersions - 1 - U, n = numVersions++;
    nodes[n] = nodes[o];
    sz[n] = sz[o];
    FOR(i, 0, 21) lift[n][i] = lift[o][i];
}

char GetLetter(int P) {
    int v = numVersions - 1;
    return getletter(v, sz[v]-1 - P);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 82552 KB Output is correct
2 Correct 86 ms 82660 KB Output is correct
3 Correct 79 ms 82660 KB Output is correct
4 Correct 86 ms 82684 KB Output is correct
5 Correct 90 ms 82756 KB Output is correct
6 Correct 106 ms 82844 KB Output is correct
7 Correct 79 ms 82844 KB Output is correct
8 Correct 87 ms 82844 KB Output is correct
9 Correct 95 ms 82844 KB Output is correct
10 Correct 104 ms 82844 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 82896 KB Output is correct
2 Correct 96 ms 82896 KB Output is correct
3 Correct 85 ms 82896 KB Output is correct
4 Correct 81 ms 82896 KB Output is correct
5 Correct 87 ms 82896 KB Output is correct
6 Correct 83 ms 82896 KB Output is correct
7 Correct 82 ms 82896 KB Output is correct
8 Correct 96 ms 82896 KB Output is correct
9 Correct 78 ms 82896 KB Output is correct
10 Correct 82 ms 82896 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 82896 KB Output is correct
2 Correct 87 ms 82956 KB Output is correct
3 Correct 83 ms 82956 KB Output is correct
4 Correct 101 ms 82956 KB Output is correct
5 Correct 91 ms 82956 KB Output is correct
6 Correct 89 ms 82956 KB Output is correct
7 Correct 91 ms 82956 KB Output is correct
8 Correct 94 ms 82956 KB Output is correct
9 Correct 82 ms 82956 KB Output is correct
10 Correct 93 ms 82956 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 86628 KB Output is correct
2 Correct 894 ms 87420 KB Output is correct
3 Correct 517 ms 87420 KB Output is correct
4 Correct 562 ms 91148 KB Output is correct
5 Correct 703 ms 91172 KB Output is correct
6 Correct 517 ms 91604 KB Output is correct
7 Correct 768 ms 91604 KB Output is correct
8 Correct 828 ms 91604 KB Output is correct
9 Correct 742 ms 91604 KB Output is correct
10 Correct 288 ms 91628 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 91628 KB Output is correct
2 Correct 801 ms 95604 KB Output is correct
3 Correct 515 ms 98608 KB Output is correct
4 Correct 585 ms 98608 KB Output is correct
5 Correct 542 ms 99096 KB Output is correct
6 Correct 603 ms 99140 KB Output is correct
7 Correct 639 ms 99184 KB Output is correct
8 Correct 812 ms 99184 KB Output is correct
9 Correct 910 ms 99184 KB Output is correct
10 Correct 254 ms 99476 KB Output is correct