oj.uz

Submission #242005

# Submission time Handle Problem Language Result Execution time Memory
242005 2020-06-26T13:43:34 Z alexandra_udristoiu Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 590 ms 90616 KB 
int nr;
int d[20][1000003], pos[1000003], num[1000003];
char s[1000003];

void Init() {}

void TypeLetter(char c) {
    nr++;
    s[nr] = c;
    pos[nr] = nr;
    num[nr] = 1 + num[nr - 1];
    d[0][nr] = pos[nr - 1];
    for(int ii = 1; ii < 20; ii++){
        d[ii][nr] = d[ii - 1][ d[ii - 1][nr] ];
    }
}

void UndoCommands(int x){
    nr++;
    pos[nr] = pos[nr - x - 1];
    num[nr] = num[nr - x - 1];
    for(int ii = 0; ii < 20; ii++){
        d[ii][nr] = d[ii][ pos[nr] ];
    }
}

char GetLetter(int p) {
    int ii, x = pos[nr];
    p = num[nr] - p - 1;
    for(ii = 19; ii >= 0; ii--){
        if(p >= (1 << ii) ){
            x = d[ii][x];
            p -= (1 << ii);
        }
    }
    return s[x];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 66520 KB Output is correct
2 Correct 317 ms 80632 KB Output is correct
3 Correct 353 ms 80992 KB Output is correct
4 Correct 475 ms 85900 KB Output is correct
5 Correct 346 ms 75024 KB Output is correct
6 Correct 251 ms 87160 KB Output is correct
7 Correct 477 ms 76920 KB Output is correct
8 Correct 391 ms 85368 KB Output is correct
9 Correct 357 ms 81432 KB Output is correct
10 Correct 225 ms 90616 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 62200 KB Output is correct
2 Correct 568 ms 55180 KB Output is correct
3 Correct 410 ms 68704 KB Output is correct
4 Correct 462 ms 61580 KB Output is correct
5 Correct 349 ms 78268 KB Output is correct
6 Correct 309 ms 80708 KB Output is correct
7 Correct 302 ms 80764 KB Output is correct
8 Correct 590 ms 69840 KB Output is correct
9 Correct 561 ms 67232 KB Output is correct
10 Correct 216 ms 89592 KB Output is correct