oj.uz

답안 #153045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153045 2019-09-11T15:24:47 Z popovicirobert 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 987 ms 86844 KB 
#include <bits/stdc++.h>

using namespace std;

static const int MAXN = (int) 1e6;

static int anc_let[20][MAXN + 1];
static int len[MAXN + 1], cur, sz;
static char let[MAXN + 1];

void Init() {
    cur = sz = 0;
    len[0] = 0;
}

void TypeLetter(char L) {
    sz++;
    let[sz] = L;
    len[sz] = len[cur] + 1;

    anc_let[0][sz] = cur;

    for(int bit = 1; bit < 20; bit++) {
        anc_let[bit][sz] = anc_let[bit - 1][anc_let[bit - 1][sz]];
    }

    cur = sz;
}

void UndoCommands(int U) {
    cur -= U;
    sz++;
    let[sz] = let[cur];
    len[sz] = len[cur];

    cur = anc_let[0][cur];
    anc_let[0][sz] = cur;

    for(int bit = 1; bit < 20; bit++) {
        anc_let[bit][sz] = anc_let[bit - 1][anc_let[bit - 1][sz]];
    }

    cur = sz;
}

char GetLetter(int P) {
    int ans = cur;
    P = len[cur] - P - 1;
    for(int bit = 0; bit < 20; bit++) {
        if(P & (1 << bit)) {
            ans = anc_let[bit][ans];
        }
    }
    return let[ans];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 4 ms 888 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 4 ms 888 KB Output is correct
10 Correct 4 ms 888 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 346 ms 60092 KB Output is correct
2 Correct 439 ms 73192 KB Output is correct
3 Correct 418 ms 72620 KB Output is correct
4 Correct 457 ms 76136 KB Output is correct
5 Correct 361 ms 67320 KB Output is correct
6 Correct 310 ms 79352 KB Output is correct
7 Correct 815 ms 68388 KB Output is correct
8 Correct 749 ms 81912 KB Output is correct
9 Correct 405 ms 78172 KB Output is correct
10 Correct 292 ms 86844 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 431 ms 55080 KB Output is correct
2 Correct 471 ms 47736 KB Output is correct
3 Correct 387 ms 60592 KB Output is correct
4 Correct 410 ms 52512 KB Output is correct
5 Correct 311 ms 70468 KB Output is correct
6 Correct 342 ms 72948 KB Output is correct
7 Correct 325 ms 72864 KB Output is correct
8 Correct 987 ms 61344 KB Output is correct
9 Correct 683 ms 64528 KB Output is correct
10 Correct 296 ms 85864 KB Output is correct