oj.uz

답안 #402961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402961 2021-05-12T15:36:51 Z Charis02 크레이피쉬 글쓰는 기계 (IOI12_scrivener) C++14
100 / 100
 778 ms 93352 KB 
#include<iostream>
#define MAX_N 1000004

using namespace std;

struct node{
    int par[21];
    int len;
    char c;
};

node trie[MAX_N];
int sz;

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

    for(int i = 1;i <= 20;i++)
        trie[cur].par[i]=-1;

    trie[cur].c = c;
    trie[cur].len = trie[par].len+1;

    return;
}

int jump(int cur,int x)
{
    if(trie[cur].par[x] != -1)
        return trie[cur].par[x];

    return trie[cur].par[x] = jump(jump(cur,x-1),x-1);
}

int get_ancestor(int cur,int x)
{
    for(int i = 20;i >= 0;i--)
    {
        if(x >= (1 << i))
            return get_ancestor(jump(cur,i),x-(1<<i));
    }

    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,trie[sz-1].len-P-1)].c;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 304 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 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 300 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 3 ms 472 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 2 ms 716 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 68456 KB Output is correct
2 Correct 208 ms 82964 KB Output is correct
3 Correct 214 ms 83100 KB Output is correct
4 Correct 279 ms 88416 KB Output is correct
5 Correct 355 ms 77252 KB Output is correct
6 Correct 234 ms 89744 KB Output is correct
7 Correct 386 ms 79204 KB Output is correct
8 Correct 304 ms 87772 KB Output is correct
9 Correct 259 ms 84044 KB Output is correct
10 Correct 206 ms 93352 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 486 ms 63808 KB Output is correct
2 Correct 533 ms 56500 KB Output is correct
3 Correct 294 ms 70740 KB Output is correct
4 Correct 350 ms 63180 KB Output is correct
5 Correct 445 ms 80524 KB Output is correct
6 Correct 386 ms 83060 KB Output is correct
7 Correct 431 ms 82944 KB Output is correct
8 Correct 650 ms 71816 KB Output is correct
9 Correct 778 ms 68892 KB Output is correct
10 Correct 212 ms 92356 KB Output is correct