oj.uz

Submission #31142

# Submission time Handle Problem Language Result Execution time Memory
31142 2017-08-11T11:04:38 Z cscandkswon Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 703 ms 92976 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int N, nod, now, cmd;
int spt[MAXN][21], A[MAXN], L[MAXN];
char let[MAXN];

void Init() {}

void TypeLetter(char c) {
    int i, p;
    A[++cmd]=now;
    let[++nod]=c;
    L[nod]=L[now]+1;
    spt[nod][0]=now;
    now=nod;
    for(i=1, p=now; ; i++){
        if(spt[spt[p][i-1]][i-1]==0) break;
        spt[p][i]=spt[spt[p][i-1]][i-1];
    }
}

void UndoCommands(int U) {
    A[++cmd]=now;
    now=A[cmd-U];
}

char GetLetter(int P) {
    int i, p=now, q=L[now]-P-1;
    for(i=20; i>=0; i--)if((1<<i)&q){
        p=spt[p][i];
    }
    return let[p];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 92976 KB Output is correct
2 Correct 633 ms 92976 KB Output is correct
3 Correct 406 ms 92976 KB Output is correct
4 Correct 333 ms 92976 KB Output is correct
5 Correct 483 ms 92976 KB Output is correct
6 Correct 319 ms 92976 KB Output is correct
7 Correct 446 ms 92976 KB Output is correct
8 Correct 416 ms 92976 KB Output is correct
9 Correct 586 ms 92976 KB Output is correct
10 Correct 166 ms 92976 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 92976 KB Output is correct
2 Correct 636 ms 92976 KB Output is correct
3 Correct 439 ms 92976 KB Output is correct
4 Correct 356 ms 92976 KB Output is correct
5 Correct 449 ms 92976 KB Output is correct
6 Correct 399 ms 92976 KB Output is correct
7 Correct 393 ms 92976 KB Output is correct
8 Correct 649 ms 92976 KB Output is correct
9 Correct 703 ms 92976 KB Output is correct
10 Correct 159 ms 92976 KB Output is correct