oj.uz

Submission #71759

# Submission time Handle Problem Language Result Execution time Memory
71759 2018-08-25T14:45:56 Z RezwanArefin01 Crayfish scrivener (IOI12_scrivener) C++17
34 / 100
 1000 ms 180196 KB 
#include <bits/stdc++.h>
using namespace std; 

const int N = 1e6 + 10; 

int t[N][26], p[N][21], idx, d[N];
int tym, node[N];  
char c[N]; 

void Init() {}

void TypeLetter(char L) {
    int u = node[tym]; 
    int &v = t[u][L - 'a'];
    if(!v) {
        v = ++idx;
        p[v][0] = u; 
        for(int i = 1; i <= 20; i++) 
            p[v][i] = p[p[v][i - 1]][i - 1]; 
    } c[v] = L; 
    node[++tym] = v; 
    d[v] = d[u] + 1; 
}

void UndoCommands(int U) {
    int u = node[tym - U]; 
    node[++tym] = u;
}

char GetLetter(int P) {
    int u = node[tym]; 
    int k = d[u] - P - 1;
    for(int i = 20; i >= 0; i--) 
        if(k >> i & 1) u = p[u][i]; 
    return c[u]; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 580 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 680 KB Output is correct
8 Correct 2 ms 772 KB Output is correct
9 Correct 3 ms 772 KB Output is correct
10 Correct 3 ms 772 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1148 KB Output is correct
2 Correct 5 ms 1160 KB Output is correct
3 Correct 5 ms 1232 KB Output is correct
4 Correct 6 ms 1628 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 5 ms 1716 KB Output is correct
7 Correct 5 ms 1740 KB Output is correct
8 Correct 7 ms 1740 KB Output is correct
9 Correct 5 ms 1744 KB Output is correct
10 Correct 4 ms 1744 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 116516 KB Output is correct
2 Correct 910 ms 131676 KB Output is correct
3 Correct 672 ms 132684 KB Output is correct
4 Correct 600 ms 132684 KB Output is correct
5 Correct 800 ms 132684 KB Output is correct
6 Correct 679 ms 161096 KB Output is correct
7 Correct 655 ms 161096 KB Output is correct
8 Correct 626 ms 161096 KB Output is correct
9 Execution timed out 1006 ms 180196 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 180196 KB Output is correct
2 Execution timed out 1052 ms 180196 KB Time limit exceeded
3 Halted 0 ms 0 KB -