oj.uz

Submission #7488

# Submission time Handle Problem Language Result Execution time Memory
7488 2014-08-09T11:11:35 Z Namnamseo Crayfish scrivener (IOI12_scrivener) C++
100 / 100
 508 ms 91900 KB 
#include <cstdio>

const int M=1000010;

char letter[M];    /// access by state
int depth[M];      /// access by state
int parent[M][21]; /// access by state
int state[M];      /// access by command

int coms, stats;

void Init(){
}

void TypeLetter(char x){
    coms++; stats++;
     state[coms ]=stats;
    letter[stats]=x;
    int myp = state[coms-1];
    parent[stats][0]=myp;
    depth[stats]=depth[myp]+1;
    int i;
    for(i=1;i<=20;i++){
        parent[stats][i]=parent[parent[stats][i-1]][i-1];
    }
}

void UndoCommands(int x){
    coms++;
    state[coms]=state[coms-1-x];
}

char GetLetter(int pos){
    int cur=state[coms];
    pos = depth[cur]-pos-1;
    int i;
    for(i=0;i<=20;i++){
        if(pos&(1<<i)){
            cur = parent[cur][i];
        }
    }
    return letter[cur];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 91900 KB Output is correct
2 Correct 420 ms 91900 KB Output is correct
3 Correct 336 ms 91900 KB Output is correct
4 Correct 320 ms 91900 KB Output is correct
5 Correct 376 ms 91900 KB Output is correct
6 Correct 320 ms 91900 KB Output is correct
7 Correct 340 ms 91900 KB Output is correct
8 Correct 348 ms 91900 KB Output is correct
9 Correct 456 ms 91900 KB Output is correct
10 Correct 216 ms 91900 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 91900 KB Output is correct
2 Correct 436 ms 91900 KB Output is correct
3 Correct 324 ms 91900 KB Output is correct
4 Correct 356 ms 91900 KB Output is correct
5 Correct 312 ms 91900 KB Output is correct
6 Correct 352 ms 91900 KB Output is correct
7 Correct 332 ms 91900 KB Output is correct
8 Correct 428 ms 91900 KB Output is correct
9 Correct 508 ms 91900 KB Output is correct
10 Correct 224 ms 91900 KB Output is correct