oj.uz

Submission #931997

# Submission time Handle Problem Language Result Execution time Memory
931997 2024-02-22T18:10:58 Z AlphaMale06 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 506 ms 98776 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

struct node{
    char c;
    int p[20];
    int h;
};

vector<node> trie;

node make(int par, char ch){
    node ret;
    ret.c=ch;
    ret.h=trie[par].h+1;
    ret.p[0]=par;
    for(int i=1; i<20; i++){
        ret.p[i]=trie[ret.p[i-1]].p[i-1];
    }
    return ret;
}


int cur=0;
const int N = 1000010;
int curs[N];
int cnt;

void Add(char c){
    curs[cnt]=trie.size();
    trie.pb(make(cur, c));
    cur=curs[cnt];
    cnt++;
}

char lift(int v, int to){
    int ret=v;
    for(int i=19; i>=0; i--){
        if(trie[trie[ret].p[i]].h >= to){
            ret=trie[ret].p[i];
        }
    }
    return trie[ret].c;
}

void TypeLetter(char c) {
    Add(c);
}

void UndoCommands(int num) {
    curs[cnt]=curs[cnt-1-num];
    cur=curs[cnt];
    cnt++;
}

char GetLetter(int ind) {
    return lift(cur, ind+1);
}

void Init() {
    node first;
    first.h=0;
    for(int i=0; i<20; i++)first.p[i]=0;
    first.c=0;
    trie.pb(first);
    curs[0]=0;
    cnt=1;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 668 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 936 KB Output is correct
7 Correct 2 ms 928 KB Output is correct
8 Correct 2 ms 820 KB Output is correct
9 Correct 2 ms 892 KB Output is correct
10 Correct 1 ms 612 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 97696 KB Output is correct
2 Correct 296 ms 98204 KB Output is correct
3 Correct 263 ms 97560 KB Output is correct
4 Correct 231 ms 52892 KB Output is correct
5 Correct 307 ms 98776 KB Output is correct
6 Correct 242 ms 97172 KB Output is correct
7 Correct 278 ms 53400 KB Output is correct
8 Correct 253 ms 53816 KB Output is correct
9 Correct 324 ms 96500 KB Output is correct
10 Correct 161 ms 52000 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 51964 KB Output is correct
2 Correct 412 ms 53156 KB Output is correct
3 Correct 240 ms 50856 KB Output is correct
4 Correct 323 ms 54740 KB Output is correct
5 Correct 232 ms 52892 KB Output is correct
6 Correct 240 ms 51880 KB Output is correct
7 Correct 273 ms 53564 KB Output is correct
8 Correct 322 ms 30116 KB Output is correct
9 Correct 506 ms 52108 KB Output is correct
10 Correct 163 ms 51816 KB Output is correct