oj.uz

답안 #1620

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1620 2013-07-10T15:19:16 Z tncks0121 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++
100 / 100
 1054 ms 152084 KB 
/*
    Solution for Scrivener, with TypeLetter and GetLetter in O(log N) and UndoCommands in O(1).
    
    Author: Matteo Boscariol
*/

#include<cstdlib>
#define MAXC 1000000
#define LOGMAXC 20

class node {
public:
    char l;
    node** parents;
    int depth;


    node(char letter, node* parent) {
        l = letter;

        if(parent == NULL) {
            depth=-1;
            parents = new node*[1];
            parents[0] = NULL;
        }
        else {
            depth=parent->depth+1;
            parents = new node*[LOGMAXC];
            parents[0] = parent;
            for(int i=1, j=2; j<=depth+1; i++, j*=2) {
                parents[i] = parents[i-1]->parents[i-1];
            }
        }
    };
};

node** command_base;
int n_commands;
node* current_position;
node* tree_root;

void Init() {
    command_base = new node*[MAXC];
    n_commands = 0;
    current_position = tree_root = new node('\0',NULL);
}

void TypeLetter(char L) {
    command_base[n_commands] = current_position;
    n_commands++;
    node* n = new node(L, current_position);
    current_position = n;
}

void UndoCommands(int U) {
    node *n = command_base[n_commands - U];
    command_base[n_commands] = current_position;
    n_commands++;
    current_position = n;
}

char GetLetter(int P)  {
    node* n = current_position;
    int distance = current_position->depth - P;

    for(int shift = LOGMAXC; shift >= 0; shift--) {
        if((distance >> shift)%2 == 1) 
          n = n->parents[shift];
    }
    return n->l;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 644 ms 126080 KB Output is correct
2 Correct 677 ms 137960 KB Output is correct
3 Correct 490 ms 135188 KB Output is correct
4 Correct 443 ms 106940 KB Output is correct
5 Correct 688 ms 117632 KB Output is correct
6 Correct 666 ms 148916 KB Output is correct
7 Correct 577 ms 72092 KB Output is correct
8 Correct 591 ms 109316 KB Output is correct
9 Correct 754 ms 152084 KB Output is correct
10 Correct 248 ms 110900 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 931 ms 107732 KB Output is correct
2 Correct 819 ms 95060 KB Output is correct
3 Correct 452 ms 104036 KB Output is correct
4 Correct 459 ms 77372 KB Output is correct
5 Correct 522 ms 113276 KB Output is correct
6 Correct 583 ms 106412 KB Output is correct
7 Correct 535 ms 113540 KB Output is correct
8 Correct 840 ms 54008 KB Output is correct
9 Correct 1054 ms 97172 KB Output is correct
10 Correct 244 ms 109844 KB Output is correct