oj.uz

답안 #76077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
76077 2018-09-12T03:30:18 Z luciocf 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 799 ms 193616 KB 
// IOI 2012 - Crayfish Scrivener
// Lúcio Cardoso

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6+10;
const int MAXL = 22;

int t, pai, nivel[MAXN], k[MAXN], tab[MAXN][MAXL];
char C[MAXN];

void Init(void)
{
    memset(tab, -1, sizeof tab);
}

void TypeLetter(char c)
{
    t++;
    k[t] = t, C[t] = c, nivel[t] = nivel[pai]+1;

    tab[t][0] = pai;
    for (int j = 1; j < MAXL; j++)
        if (tab[t][j-1] != -1)
            tab[t][j] = tab[tab[t][j-1]][j-1];
    pai = t;
}

void UndoCommands(int u)
{
    k[t+1] = k[t-u];
    t++;
    pai = k[t];
}

char GetLetter(int p)
{
    if (p+1 == nivel[k[t]]) return C[k[t]];

    int u = k[t];
    p = nivel[k[t]]-p-1;
    for (int i = MAXL-1; i >= 0; i--)
        if (p-(1<<i) >= 0)
            u = tab[u][i], p -= (1<<i);
    return C[u];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 86396 KB Output is correct
2 Correct 70 ms 86544 KB Output is correct
3 Correct 67 ms 86608 KB Output is correct
4 Correct 74 ms 86668 KB Output is correct
5 Correct 67 ms 86668 KB Output is correct
6 Correct 68 ms 86668 KB Output is correct
7 Correct 69 ms 86668 KB Output is correct
8 Correct 70 ms 86688 KB Output is correct
9 Correct 69 ms 86784 KB Output is correct
10 Correct 69 ms 86892 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 86892 KB Output is correct
2 Correct 69 ms 86892 KB Output is correct
3 Correct 70 ms 86892 KB Output is correct
4 Correct 69 ms 86892 KB Output is correct
5 Correct 68 ms 86908 KB Output is correct
6 Correct 70 ms 86940 KB Output is correct
7 Correct 68 ms 86940 KB Output is correct
8 Correct 68 ms 86940 KB Output is correct
9 Correct 68 ms 86940 KB Output is correct
10 Correct 72 ms 86940 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 86960 KB Output is correct
2 Correct 71 ms 86972 KB Output is correct
3 Correct 70 ms 87012 KB Output is correct
4 Correct 78 ms 87056 KB Output is correct
5 Correct 70 ms 87056 KB Output is correct
6 Correct 76 ms 87140 KB Output is correct
7 Correct 74 ms 87184 KB Output is correct
8 Correct 73 ms 87184 KB Output is correct
9 Correct 68 ms 87212 KB Output is correct
10 Correct 70 ms 87236 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 514 ms 97372 KB Output is correct
2 Correct 576 ms 102760 KB Output is correct
3 Correct 425 ms 107620 KB Output is correct
4 Correct 424 ms 114168 KB Output is correct
5 Correct 527 ms 118100 KB Output is correct
6 Correct 492 ms 123272 KB Output is correct
7 Correct 534 ms 128168 KB Output is correct
8 Correct 569 ms 134140 KB Output is correct
9 Correct 655 ms 138164 KB Output is correct
10 Correct 304 ms 143088 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 145044 KB Output is correct
2 Correct 743 ms 149712 KB Output is correct
3 Correct 432 ms 156152 KB Output is correct
4 Correct 456 ms 162300 KB Output is correct
5 Correct 516 ms 168460 KB Output is correct
6 Correct 474 ms 173268 KB Output is correct
7 Correct 466 ms 177432 KB Output is correct
8 Correct 642 ms 182456 KB Output is correct
9 Correct 799 ms 187820 KB Output is correct
10 Correct 265 ms 193616 KB Output is correct