oj.uz

Submission #49531

# Submission time Handle Problem Language Result Execution time Memory
49531 2018-05-30T08:33:06 Z ho94949 Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 923 ms 179004 KB 
const int lgMAXN = 20;
const int MAXN = 1 << 20;
int len;
int arr[MAXN];
int sparse[MAXN][lgMAXN];


void Init() {
    len = 0;
}

void TypeLetter(char L) {
    arr[++len] = L;
    sparse[len][0] = len;
    for(int i=1; i<lgMAXN; ++i)
        if(sparse[len][i-1] == 0) sparse[len][i] = 0;
        else sparse[len][i] = sparse[sparse[len][i-1]-1][i-1];
}

void UndoCommands(int U) {
    arr[++len] = -U;
    for(int i=0; i<lgMAXN; ++i)
        sparse[len][i] = sparse[len-U-1][i];
}

char GetLetter(int P) {
    
    int c = 0, idx = len;
    for(int i=lgMAXN-1; i>=0; --i)
        if(sparse[idx][i])
        {
            c += (1<<i);
            idx = sparse[idx][i]-1;
        }

    int ans = len;
    for(int i=lgMAXN-1; i>=0; --i)
        if((c-P)&(1<<i))
            ans = sparse[ans][i]-1;
    
    return arr[ans+1];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 2 ms 648 KB Output is correct
10 Correct 2 ms 788 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 4 ms 1064 KB Output is correct
3 Correct 3 ms 1112 KB Output is correct
4 Correct 3 ms 1260 KB Output is correct
5 Correct 4 ms 1260 KB Output is correct
6 Correct 3 ms 1356 KB Output is correct
7 Correct 3 ms 1368 KB Output is correct
8 Correct 3 ms 1408 KB Output is correct
9 Correct 3 ms 1444 KB Output is correct
10 Correct 3 ms 1456 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 63624 KB Output is correct
2 Correct 761 ms 80588 KB Output is correct
3 Correct 501 ms 84836 KB Output is correct
4 Correct 419 ms 94548 KB Output is correct
5 Correct 441 ms 94548 KB Output is correct
6 Correct 401 ms 106356 KB Output is correct
7 Correct 596 ms 106356 KB Output is correct
8 Correct 542 ms 114944 KB Output is correct
9 Correct 537 ms 116220 KB Output is correct
10 Correct 250 ms 129356 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 129356 KB Output is correct
2 Correct 923 ms 129356 KB Output is correct
3 Correct 392 ms 129356 KB Output is correct
4 Correct 434 ms 129356 KB Output is correct
5 Correct 489 ms 143316 KB Output is correct
6 Correct 450 ms 150164 KB Output is correct
7 Correct 472 ms 154484 KB Output is correct
8 Correct 593 ms 154484 KB Output is correct
9 Correct 716 ms 154484 KB Output is correct
10 Correct 245 ms 179004 KB Output is correct