oj.uz

답안 #511424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
511424 2022-01-15T18:46:42 Z tabr 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++17
100 / 100
 441 ms 163956 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

const int N = (int) 1e6 + 10;

char node[N];
int trie[N][26];
int pv[N][20];
int depth[N];
int lg[N];
int id;
int sz;

void Init() {
    node[0] = '!';
    memset(trie, -1, sizeof(trie));
    id = 1;
    sz = 1;
}

void TypeLetter(char ll) {
    int v = lg[id - 1];
    int l = ll - 'a';
    if (trie[v][l] != -1) {
        lg[id] = trie[v][l];
        id++;
        return;
    }
    int to = sz;
    trie[v][l] = to;
    depth[to] = depth[v] + 1;
    lg[id] = to;
    pv[to][0] = v;
    for (int i = 1; i < 20; i++) {
        pv[to][i] = pv[pv[to][i - 1]][i - 1];
    }
    node[to] = ll;
    id++;
    sz++;
}

void UndoCommands(int u) {
    lg[id] = lg[id - 1 - u];
    id++;
}

char GetLetter(int p) {
    int v = lg[id - 1];
    int up = depth[v] - 1 - p;
    for (int i = 19; i >= 0; i--) {
        if (up & (1 << i)) {
            v = pv[v][i];
        }
    }
    return node[v];
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Init();
    TypeLetter('a');
    TypeLetter('b');
    cout << GetLetter(1) << '\n';
    TypeLetter('d');
    UndoCommands(2);
    UndoCommands(1);
    cout << GetLetter(2) << '\n';
    TypeLetter('e');
    UndoCommands(1);
    UndoCommands(5);
    TypeLetter('c');
    cout << GetLetter(2) << '\n';
    UndoCommands(2);
    cout << GetLetter(2) << '\n';
    return 0;
}
#endif

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 102064 KB Output is correct
2 Correct 39 ms 101988 KB Output is correct
3 Correct 41 ms 102064 KB Output is correct
4 Correct 39 ms 101988 KB Output is correct
5 Correct 40 ms 102052 KB Output is correct
6 Correct 40 ms 101976 KB Output is correct
7 Correct 40 ms 102036 KB Output is correct
8 Correct 38 ms 102052 KB Output is correct
9 Correct 39 ms 102044 KB Output is correct
10 Correct 41 ms 102084 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 101964 KB Output is correct
2 Correct 39 ms 102052 KB Output is correct
3 Correct 40 ms 102028 KB Output is correct
4 Correct 39 ms 102052 KB Output is correct
5 Correct 43 ms 101956 KB Output is correct
6 Correct 41 ms 102088 KB Output is correct
7 Correct 41 ms 102032 KB Output is correct
8 Correct 39 ms 101964 KB Output is correct
9 Correct 41 ms 102072 KB Output is correct
10 Correct 39 ms 101980 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 102212 KB Output is correct
2 Correct 41 ms 102244 KB Output is correct
3 Correct 44 ms 102240 KB Output is correct
4 Correct 42 ms 102272 KB Output is correct
5 Correct 40 ms 102196 KB Output is correct
6 Correct 41 ms 102380 KB Output is correct
7 Correct 44 ms 102340 KB Output is correct
8 Correct 40 ms 102344 KB Output is correct
9 Correct 41 ms 102256 KB Output is correct
10 Correct 41 ms 102180 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 324 ms 153208 KB Output is correct
2 Correct 359 ms 158148 KB Output is correct
3 Correct 312 ms 156616 KB Output is correct
4 Correct 307 ms 143500 KB Output is correct
5 Correct 311 ms 149568 KB Output is correct
6 Correct 285 ms 162716 KB Output is correct
7 Correct 290 ms 131708 KB Output is correct
8 Correct 299 ms 147236 KB Output is correct
9 Correct 398 ms 163956 KB Output is correct
10 Correct 237 ms 147820 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 388 ms 145348 KB Output is correct
2 Correct 441 ms 140100 KB Output is correct
3 Correct 312 ms 148708 KB Output is correct
4 Correct 323 ms 138308 KB Output is correct
5 Correct 287 ms 152648 KB Output is correct
6 Correct 295 ms 149480 KB Output is correct
7 Correct 302 ms 152628 KB Output is correct
8 Correct 366 ms 129948 KB Output is correct
9 Correct 424 ms 147208 KB Output is correct
10 Correct 233 ms 151480 KB Output is correct