oj.uz

Submission #7276

# Submission time Handle Problem Language Result Execution time Memory
7276 2014-07-29T06:33:36 Z myungwoo Crayfish scrivener (IOI12_scrivener) C++
100 / 100
 684 ms 130332 KB 
#include <stdlib.h>
#include <stdio.h>

#define MAXK 1000006

static int K;

static struct STATE{
    int len;
    char letter;
    STATE *prev[20];
} *state[MAXK];

void Init() {}

STATE *make(int len, char letter, STATE *prev)
{
    STATE *ret=(STATE*)malloc(sizeof(STATE));
    ret->len = len; ret->letter = letter;
    for (int i=0;i<20;i++) ret->prev[i] = NULL;
    ret->prev[0] = prev;
    for (int i=0;i<19&&ret->prev[i];i++){
        ret->prev[i+1] = ret->prev[i]->prev[i];
    }
    return ret;
}

void TypeLetter(char letter)
{
    STATE *tmp;
    if (state[K]) tmp = make(state[K]->len+1,letter,state[K]);
    else tmp = make(1,letter,NULL);
    state[++K] = tmp;
}

void UndoCommands(int steps)
{
    state[++K] = state[K-steps-1];
}

char GetLetter(int pos)
{
    STATE *now=state[K];
    int bef=now->len-pos-1,i;
    for (i=20;i--;) if ((bef>>i)&1){
        now = now->prev[i];
    }
    return now->letter;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8892 KB Output is correct
2 Correct 0 ms 9024 KB Output is correct
3 Correct 0 ms 9024 KB Output is correct
4 Correct 0 ms 9024 KB Output is correct
5 Correct 0 ms 9024 KB Output is correct
6 Correct 0 ms 9024 KB Output is correct
7 Correct 0 ms 9024 KB Output is correct
8 Correct 0 ms 9024 KB Output is correct
9 Correct 0 ms 9024 KB Output is correct
10 Correct 0 ms 9024 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8892 KB Output is correct
2 Correct 0 ms 9024 KB Output is correct
3 Correct 0 ms 9024 KB Output is correct
4 Correct 0 ms 9024 KB Output is correct
5 Correct 0 ms 9024 KB Output is correct
6 Correct 0 ms 9024 KB Output is correct
7 Correct 0 ms 9024 KB Output is correct
8 Correct 0 ms 9024 KB Output is correct
9 Correct 0 ms 9024 KB Output is correct
10 Correct 0 ms 9024 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9156 KB Output is correct
2 Correct 0 ms 9156 KB Output is correct
3 Correct 0 ms 9288 KB Output is correct
4 Correct 0 ms 9420 KB Output is correct
5 Correct 0 ms 9288 KB Output is correct
6 Correct 0 ms 9552 KB Output is correct
7 Correct 0 ms 9552 KB Output is correct
8 Correct 0 ms 9420 KB Output is correct
9 Correct 0 ms 9420 KB Output is correct
10 Correct 0 ms 9156 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 108288 KB Output is correct
2 Correct 468 ms 118320 KB Output is correct
3 Correct 360 ms 115944 KB Output is correct
4 Correct 352 ms 92052 KB Output is correct
5 Correct 428 ms 101160 KB Output is correct
6 Correct 484 ms 127560 KB Output is correct
7 Correct 448 ms 62616 KB Output is correct
8 Correct 492 ms 94032 KB Output is correct
9 Correct 596 ms 130332 KB Output is correct
10 Correct 204 ms 95484 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 92844 KB Output is correct
2 Correct 612 ms 82020 KB Output is correct
3 Correct 316 ms 89676 KB Output is correct
4 Correct 352 ms 67104 KB Output is correct
5 Correct 432 ms 97464 KB Output is correct
6 Correct 384 ms 91656 KB Output is correct
7 Correct 404 ms 97728 KB Output is correct
8 Correct 524 ms 47304 KB Output is correct
9 Correct 684 ms 83868 KB Output is correct
10 Correct 208 ms 94560 KB Output is correct