oj.uz

Submission #1622

# Submission time Handle Problem Language Result Execution time Memory
1622 2013-07-10T15:21:17 Z tncks0121 Crayfish scrivener (IOI12_scrivener) C++
100 / 100
 732 ms 130036 KB 
#include<stdio.h>
 
const int MAXC = 1000005;
const int lgMAXC = 20;
 
struct node{
    char letter;
    int level;
    node* parent[lgMAXC];
 
    node(char letter, node* par): letter(letter){
        parent[0] = par; 
        if(par != NULL) level = par->level + 1; else level = 0;
        for(int i=1; i<lgMAXC; i++){
            if(parent[i-1] == NULL) parent[i] = NULL;
            else parent[i] = parent[i-1]->parent[i-1];
        }
    }
};
 
node* Commands[MAXC];
node* now;
int N;
 
void Init(){
    now = new node(0, NULL);
    Commands[1] = now; N = 1;
}
 
void TypeLetter(char L){
    Commands[++N] = new node(L, now);
    now = Commands[N];
}
 
void UndoCommands(int U){
    int val = N - U; Commands[++N] = Commands[val];
    now = Commands[N];
}
 
char GetLetter(int P){ ++P;
    node* tmp = now; int L = now->level - P;
    for(int i=0; (1<<i)<=L; i++) if(L & (1<<i)){
        tmp = tmp->parent[i];
    }
    return tmp->letter;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 107992 KB Output is correct
2 Correct 621 ms 118024 KB Output is correct
3 Correct 473 ms 115648 KB Output is correct
4 Correct 369 ms 91756 KB Output is correct
5 Correct 433 ms 100864 KB Output is correct
6 Correct 558 ms 127264 KB Output is correct
7 Correct 568 ms 62320 KB Output is correct
8 Correct 617 ms 93868 KB Output is correct
9 Correct 584 ms 130036 KB Output is correct
10 Correct 248 ms 95188 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 92548 KB Output is correct
2 Correct 683 ms 81724 KB Output is correct
3 Correct 358 ms 89380 KB Output is correct
4 Correct 449 ms 66808 KB Output is correct
5 Correct 412 ms 97168 KB Output is correct
6 Correct 444 ms 91360 KB Output is correct
7 Correct 389 ms 97432 KB Output is correct
8 Correct 508 ms 47008 KB Output is correct
9 Correct 732 ms 83572 KB Output is correct
10 Correct 267 ms 94264 KB Output is correct