oj.uz

Submission #258798

# Submission time Handle Problem Language Result Execution time Memory
258798 2020-08-06T14:57:35 Z SamAnd Crayfish scrivener (IOI12_scrivener) C++17
100 / 100
 635 ms 67424 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 1000006, m = 20;

int z;
char a[N];
int p[N][m];
int d[N];

vector<int> v;

void Init()
{
    v.push_back(0);
}

void TypeLetter(char L)
{
    ++z;
    a[z] = L;
    p[z][0] = v.back();
    d[z] = d[v.back()] + 1;
    for (int i = 1; i < m; ++i)
        p[z][i] = p[p[z][i - 1]][i - 1];
    v.push_back(z);
}

void UndoCommands(int U)
{
    v.push_back(v[sz(v) - U - 1]);
}

char GetLetter(int P)
{
    ++P;
    int x = v.back();
    for (int i = m - 1; i >= 0; --i)
    {
        if (d[p[x][i]] >= P)
            x = p[x][i];
    }
    return a[x];
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 55400 KB Output is correct
2 Correct 416 ms 61160 KB Output is correct
3 Correct 357 ms 60640 KB Output is correct
4 Correct 384 ms 50964 KB Output is correct
5 Correct 454 ms 53476 KB Output is correct
6 Correct 327 ms 65888 KB Output is correct
7 Correct 413 ms 35936 KB Output is correct
8 Correct 367 ms 50784 KB Output is correct
9 Correct 450 ms 67424 KB Output is correct
10 Correct 260 ms 50272 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 48736 KB Output is correct
2 Correct 635 ms 44220 KB Output is correct
3 Correct 389 ms 48224 KB Output is correct
4 Correct 455 ms 38500 KB Output is correct
5 Correct 359 ms 51552 KB Output is correct
6 Correct 397 ms 48912 KB Output is correct
7 Correct 410 ms 51680 KB Output is correct
8 Correct 522 ms 28444 KB Output is correct
9 Correct 634 ms 45596 KB Output is correct
10 Correct 280 ms 49888 KB Output is correct