oj.uz

Submission #402976

# Submission time Handle Problem Language Result Execution time Memory
402976 2021-05-12T15:46:02 Z Charis02 Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 995 ms 15856 KB 
#include<iostream>
#define MAX_N 1000004

using namespace std;

struct node{
    int par;
    int sqpar;
    int len;
    char c;
};

node trie[MAX_N];
int sz;
const int sqrt = 800;

void init_node(int cur,int par,char c)
{
    trie[cur].par = par;
    trie[cur].c = c;
    trie[cur].len = trie[par].len+1;

    if(trie[cur].len%sqrt == 0)
        trie[cur].sqpar = par;
    else
        trie[cur].sqpar = trie[par].sqpar;

    return;
}

int get_ancestor(int cur,int x)
{
    while(trie[trie[cur].sqpar].len >= x)
        cur = trie[cur].sqpar;

    while(trie[cur].len > x)
        cur = trie[cur].par;

    return cur;
}

void Init()
{
    init_node(0,0,'-');
    trie[0].len = 0;
    sz = 1;
    return;
}

void TypeLetter(char L)
{
    init_node(sz,sz-1,L);
    sz++;

    return;
}

void UndoCommands(int U)
{
    trie[sz] = trie[sz-U-1];
    sz++;

    return;
}

char GetLetter(int P)
{
   // cout << "here " << P << " " << sz-1 << " " << trie[sz-1].len << " " << get_ancestor(sz-1,trie[sz-1].len-P-1) << endl;
    return trie[get_ancestor(sz-1,P+1)].c;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 11660 KB Output is correct
2 Correct 271 ms 14156 KB Output is correct
3 Correct 162 ms 13984 KB Output is correct
4 Correct 204 ms 14724 KB Output is correct
5 Correct 896 ms 13276 KB Output is correct
6 Correct 426 ms 15320 KB Output is correct
7 Correct 995 ms 13336 KB Output is correct
8 Correct 697 ms 14788 KB Output is correct
9 Correct 568 ms 14320 KB Output is correct
10 Correct 206 ms 15856 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 11100 KB Output is correct
2 Correct 948 ms 9896 KB Output is correct
3 Correct 235 ms 12120 KB Output is correct
4 Correct 279 ms 10976 KB Output is correct
5 Correct 313 ms 13896 KB Output is correct
6 Correct 332 ms 14368 KB Output is correct
7 Correct 382 ms 14404 KB Output is correct
8 Correct 797 ms 12384 KB Output is correct
9 Correct 855 ms 11920 KB Output is correct
10 Correct 165 ms 15788 KB Output is correct