oj.uz

Submission #897887

# Submission time Handle Problem Language Result Execution time Memory
897887 2024-01-03T23:03:56 Z aykhn Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 339 ms 166848 KB 
#include <bits/stdc++.h>
 
// author: aykhn
 
using namespace std;
 
#define mpr make_pair
#define pb push_back
#define fi first
#define se second
 
const int MXN = 1e6 + 5;
const int LOG = 21;
 
int n;
int adj[MXN][26];
int p[LOG][MXN];
char val[MXN];
int dep[MXN];
vector<int> s;
 
void Init() 
{
    s.clear();
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j < LOG; j++) p[j][i] = 0;
        for (int j = 0; j < 26; j++) adj[i][j] = 0;
        val[i] = '$';
    }
    s.pb(0);
    n = 0;
}
 
void TypeLetter(char L) 
{
    int cur = s.back();
    if (adj[cur][L - 'a']) s.pb(adj[cur][L - 'a']);
    else 
    {
        adj[cur][L - 'a'] = ++n;
        p[0][n] = cur;
        for (int i = 1; i < LOG; i++) p[i][n] = p[i - 1][p[i - 1][n]];
        dep[n] = dep[cur] + 1;
        val[n] = L;
        s.pb(n);
    }
}
 
void UndoCommands(int U) 
{
    s.pb(s[(int)s.size() - U - 1]);
}
 
char GetLetter(int P) 
{   
    int cur = s.back();
    int d = dep[cur] - P - 1;
    for (int i = LOG - 1; i >= 0; i--)
    {
        if (d >> i & 1) cur = p[i][cur];
    }
    return val[cur];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 47452 KB Output is correct
2 Correct 6 ms 47960 KB Output is correct
3 Correct 6 ms 47708 KB Output is correct
4 Correct 6 ms 47668 KB Output is correct
5 Correct 6 ms 47708 KB Output is correct
6 Correct 6 ms 47876 KB Output is correct
7 Correct 6 ms 47708 KB Output is correct
8 Correct 6 ms 47708 KB Output is correct
9 Correct 6 ms 47704 KB Output is correct
10 Correct 6 ms 47708 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 151304 KB Output is correct
2 Correct 240 ms 159844 KB Output is correct
3 Correct 204 ms 158144 KB Output is correct
4 Correct 196 ms 139464 KB Output is correct
5 Correct 197 ms 150032 KB Output is correct
6 Correct 178 ms 164800 KB Output is correct
7 Correct 196 ms 115140 KB Output is correct
8 Correct 197 ms 146856 KB Output is correct
9 Correct 227 ms 166848 KB Output is correct
10 Correct 144 ms 146620 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 143384 KB Output is correct
2 Correct 339 ms 132728 KB Output is correct
3 Correct 223 ms 139312 KB Output is correct
4 Correct 199 ms 115588 KB Output is correct
5 Correct 186 ms 148284 KB Output is correct
6 Correct 229 ms 141660 KB Output is correct
7 Correct 208 ms 147636 KB Output is correct
8 Correct 230 ms 97728 KB Output is correct
9 Correct 272 ms 136636 KB Output is correct
10 Correct 154 ms 146256 KB Output is correct