oj.uz

Submission #114971

# Submission time Handle Problem Language Result Execution time Memory
114971 2019-06-04T08:22:03 Z zoooma13 Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
 1000 ms 182648 KB 
#include <bits/stdc++.h>
using namespace std;

//#include "grader.cpp"

#define MAX_COMM 1000006
#define LOG_COMM 22

int curr_comm;
char edg_char[MAX_COMM];
int par[LOG_COMM][MAX_COMM] ,dist[LOG_COMM][MAX_COMM];
int dist_root[MAX_COMM];

void bld_anc(int u ,int p ,int v){
    par[0][u] = p;
    dist[0][u] = (bool)v;
    dist_root[u] = dist_root[p]+(bool)v;
    edg_char[u] = (v ? v : edg_char[p]);
    for(int i=1; i<LOG_COMM; i++)
        if(~par[i-1][u]){
            par[i][u] = par[i-1][par[i-1][u]];
            dist[i][u] = dist[i-1][u] + dist[i-1][par[i-1][u]];
        }
}

void Init(){
    curr_comm = 0;
    memset(par ,-1 ,sizeof par);
    memset(dist ,0 ,sizeof dist);
    memset(dist_root ,0 ,sizeof dist_root);
}
void TypeLetter(char L){++curr_comm;
    bld_anc(curr_comm ,curr_comm-1 ,L);
}
void UndoCommands(int U){++curr_comm;
    bld_anc(curr_comm ,curr_comm-U-1 ,0);
}

char GetLetter(int P){
    int u = curr_comm;
    P = dist_root[u]-P-1;
    for(int i=LOG_COMM-1; ~i; i--)
        if(~par[i][u] && dist[i][u] <= P){
            P -= dist[i][u];
            u = par[i][u];
        }
    return edg_char[u];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 176504 KB Output is correct
2 Correct 127 ms 176572 KB Output is correct
3 Correct 132 ms 176424 KB Output is correct
4 Correct 131 ms 176504 KB Output is correct
5 Correct 126 ms 176504 KB Output is correct
6 Correct 127 ms 176512 KB Output is correct
7 Correct 132 ms 176376 KB Output is correct
8 Correct 135 ms 176520 KB Output is correct
9 Correct 146 ms 176376 KB Output is correct
10 Correct 134 ms 176540 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 176496 KB Output is correct
2 Correct 135 ms 176512 KB Output is correct
3 Correct 131 ms 176388 KB Output is correct
4 Correct 135 ms 176540 KB Output is correct
5 Correct 126 ms 176600 KB Output is correct
6 Correct 126 ms 176504 KB Output is correct
7 Correct 127 ms 176504 KB Output is correct
8 Correct 126 ms 176364 KB Output is correct
9 Correct 128 ms 176380 KB Output is correct
10 Correct 127 ms 176376 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 176376 KB Output is correct
2 Correct 134 ms 176508 KB Output is correct
3 Correct 129 ms 176476 KB Output is correct
4 Correct 132 ms 176476 KB Output is correct
5 Correct 130 ms 176472 KB Output is correct
6 Correct 131 ms 176612 KB Output is correct
7 Correct 135 ms 176432 KB Output is correct
8 Correct 132 ms 176572 KB Output is correct
9 Correct 131 ms 176632 KB Output is correct
10 Correct 130 ms 176528 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 177940 KB Output is correct
2 Correct 661 ms 177780 KB Output is correct
3 Correct 560 ms 177824 KB Output is correct
4 Correct 636 ms 177912 KB Output is correct
5 Correct 677 ms 178108 KB Output is correct
6 Correct 513 ms 178004 KB Output is correct
7 Execution timed out 1084 ms 177944 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 825 ms 178288 KB Output is correct
2 Correct 998 ms 182608 KB Output is correct
3 Correct 591 ms 182480 KB Output is correct
4 Correct 658 ms 182648 KB Output is correct
5 Correct 565 ms 182344 KB Output is correct
6 Correct 576 ms 182304 KB Output is correct
7 Correct 569 ms 182424 KB Output is correct
8 Execution timed out 1094 ms 182388 KB Time limit exceeded
9 Halted 0 ms 0 KB -