oj.uz

Submission #114977

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

//#include "grader.cpp"

#define MAX_COMM 1000006
#define LOG_COMM 20

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

void bld_anc(int u ,int p ,int v){
    par[u][0] = p;
    dist[u][0] = (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[u][i-1]){
            par[u][i] = par[par[u][i-1]][i-1];
            dist[u][i] = dist[u][i-1] + dist[par[u][i-1]][i-1];
        }
}

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[u][i] && dist[u][i] <= P){
            P -= dist[u][i];
            u = par[u][i];
        }
    return edg_char[u];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 160760 KB Output is correct
2 Correct 120 ms 160764 KB Output is correct
3 Correct 120 ms 160812 KB Output is correct
4 Correct 116 ms 160744 KB Output is correct
5 Correct 116 ms 160828 KB Output is correct
6 Correct 121 ms 160760 KB Output is correct
7 Correct 115 ms 160760 KB Output is correct
8 Correct 120 ms 160764 KB Output is correct
9 Correct 121 ms 160900 KB Output is correct
10 Correct 118 ms 160812 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 160840 KB Output is correct
2 Correct 118 ms 160828 KB Output is correct
3 Correct 116 ms 160800 KB Output is correct
4 Correct 115 ms 160924 KB Output is correct
5 Correct 116 ms 160828 KB Output is correct
6 Correct 116 ms 160832 KB Output is correct
7 Correct 122 ms 160768 KB Output is correct
8 Correct 122 ms 160760 KB Output is correct
9 Correct 116 ms 160796 KB Output is correct
10 Correct 120 ms 160760 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 160804 KB Output is correct
2 Correct 125 ms 160960 KB Output is correct
3 Correct 127 ms 160780 KB Output is correct
4 Correct 122 ms 160804 KB Output is correct
5 Correct 120 ms 160832 KB Output is correct
6 Correct 123 ms 160860 KB Output is correct
7 Correct 118 ms 160888 KB Output is correct
8 Correct 118 ms 160780 KB Output is correct
9 Correct 121 ms 160888 KB Output is correct
10 Correct 123 ms 160840 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 161728 KB Output is correct
2 Correct 932 ms 161968 KB Output is correct
3 Correct 675 ms 161916 KB Output is correct
4 Correct 692 ms 161952 KB Output is correct
5 Correct 846 ms 162268 KB Output is correct
6 Correct 542 ms 162168 KB Output is correct
7 Execution timed out 1079 ms 161584 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 162268 KB Time limit exceeded
2 Halted 0 ms 0 KB -