oj.uz

답안 #71762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71762 2018-08-25T14:50:11 Z RezwanArefin01 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++17
100 / 100
 966 ms 151392 KB 
#include <bits/stdc++.h>
using namespace std; 

const int N = 1e6 + 10; 

int t[N][26], p[N][21], idx, d[N];
int tym, node[N], lsb[N], lg[N];  
char c[N]; 

void Init() {
    lg[1] = 0; 
    for(int i = 2; i < N; i++) 
        lg[i] = lg[i >> 1] + 1; 
    for(int i = 1; i < N; i++) 
        lsb[i] = lg[i & -i]; 
}

void TypeLetter(char L) {
    int u = node[tym]; 
    int &v = t[u][L - 'a'];
    if(!v) {
        v = ++idx;
        p[v][0] = u; 
        for(int i = 1; i <= 20 && p[v][i - 1]; i++) 
            p[v][i] = p[p[v][i - 1]][i - 1]; 
    } c[v] = L; 
    node[++tym] = v; 
    d[v] = d[u] + 1; 
}

void UndoCommands(int U) {
    int u = node[tym - U]; 
    node[++tym] = u;
}

char GetLetter(int P) {
    int u = node[tym]; 
    int k = d[u] - P - 1;
    while(k) {
        u = p[u][lsb[k]]; 
        k ^= k & -k;
    } return c[u]; 
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 8188 KB Output is correct
2 Correct 14 ms 8188 KB Output is correct
3 Correct 11 ms 8200 KB Output is correct
4 Correct 12 ms 8204 KB Output is correct
5 Correct 9 ms 8276 KB Output is correct
6 Correct 12 ms 8472 KB Output is correct
7 Correct 9 ms 8472 KB Output is correct
8 Correct 11 ms 8472 KB Output is correct
9 Correct 12 ms 8484 KB Output is correct
10 Correct 13 ms 8484 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8484 KB Output is correct
2 Correct 10 ms 8484 KB Output is correct
3 Correct 12 ms 8484 KB Output is correct
4 Correct 11 ms 8556 KB Output is correct
5 Correct 12 ms 8556 KB Output is correct
6 Correct 10 ms 8556 KB Output is correct
7 Correct 10 ms 8556 KB Output is correct
8 Correct 10 ms 8556 KB Output is correct
9 Correct 13 ms 8556 KB Output is correct
10 Correct 12 ms 8556 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 8684 KB Output is correct
2 Correct 10 ms 8684 KB Output is correct
3 Correct 13 ms 8684 KB Output is correct
4 Correct 11 ms 8940 KB Output is correct
5 Correct 13 ms 8940 KB Output is correct
6 Correct 16 ms 9068 KB Output is correct
7 Correct 14 ms 9172 KB Output is correct
8 Correct 14 ms 9172 KB Output is correct
9 Correct 14 ms 9172 KB Output is correct
10 Correct 12 ms 9172 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 922 ms 120092 KB Output is correct
2 Correct 918 ms 131352 KB Output is correct
3 Correct 548 ms 131352 KB Output is correct
4 Correct 581 ms 131352 KB Output is correct
5 Correct 633 ms 131352 KB Output is correct
6 Correct 576 ms 140956 KB Output is correct
7 Correct 695 ms 140956 KB Output is correct
8 Correct 623 ms 140956 KB Output is correct
9 Correct 954 ms 144428 KB Output is correct
10 Correct 364 ms 144428 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 882 ms 144428 KB Output is correct
2 Correct 889 ms 144428 KB Output is correct
3 Correct 530 ms 144428 KB Output is correct
4 Correct 529 ms 144428 KB Output is correct
5 Correct 615 ms 144428 KB Output is correct
6 Correct 584 ms 144428 KB Output is correct
7 Correct 617 ms 144428 KB Output is correct
8 Correct 843 ms 144428 KB Output is correct
9 Correct 966 ms 144428 KB Output is correct
10 Correct 328 ms 151392 KB Output is correct