oj.uz

Submission #137462

# Submission time Handle Problem Language Result Execution time Memory
137462 2019-07-27T20:13:55 Z MladenP Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 883 ms 145504 KB 
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 1000010
#define MAXL 22
int trie[MAXN][27], anc[MAXN][MAXL], dub[MAXN];
vector<int> op;
int timer = 0;
void Init() {
    timer = 1;
    op.pb(1);
}

void TypeLetter(char L) {
    int c = L-'a'+1, cur = op.back();
    if(trie[cur][c] == 0) {
        trie[cur][c] = ++timer;
        anc[timer][0] = cur;
        dub[timer] = dub[cur] + 1;
        for(int i = 1; i < MAXL; i++) anc[timer][i] = anc[anc[timer][i-1]][i-1];
    }
    op.pb(trie[cur][c]);
}

void UndoCommands(int U) {
    op.pb(op[sz(op)-1-U]);
}

char GetLetter(int P) {
    int cur = op.back();
    P = dub[cur] - 1 - P;
    for(int k = MAXL-1; k >= 0; k--) {
        if((1<<k) <= P) {
            cur = anc[cur][k];
            P -= (1<<k);
        }
    }
    int par = anc[cur][0];
    for(int i = 1; i < 27; i++) {
        if(trie[par][i] == cur) return ('a'+i-1);
    }
}

Compilation message

scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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 376 KB Output is correct

Subtask #2
7.0 / 7.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 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 760 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 4 ms 988 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 4 ms 1144 KB Output is correct
8 Correct 4 ms 888 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 3 ms 632 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 119596 KB Output is correct
2 Correct 695 ms 131464 KB Output is correct
3 Correct 493 ms 128392 KB Output is correct
4 Correct 490 ms 98864 KB Output is correct
5 Correct 654 ms 111732 KB Output is correct
6 Correct 509 ms 141668 KB Output is correct
7 Correct 562 ms 71112 KB Output is correct
8 Correct 563 ms 106532 KB Output is correct
9 Correct 734 ms 145504 KB Output is correct
10 Correct 320 ms 106720 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 102676 KB Output is correct
2 Correct 869 ms 91488 KB Output is correct
3 Correct 509 ms 98488 KB Output is correct
4 Correct 478 ms 72732 KB Output is correct
5 Correct 644 ms 108564 KB Output is correct
6 Correct 533 ms 101244 KB Output is correct
7 Correct 536 ms 108356 KB Output is correct
8 Correct 635 ms 53612 KB Output is correct
9 Correct 883 ms 94696 KB Output is correct
10 Correct 305 ms 106028 KB Output is correct