oj.uz

Submission #172112

# Submission time Handle Problem Language Result Execution time Memory
172112 2019-12-31T07:30:53 Z arnold518 Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 933 ms 214736 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const int MAXM = 20;

struct Node
{
    int dep; char c;
    int par[MAXM+1], chd[30];

    Node()
    {
        int i, j;
        dep=0; c='!';
        for(i=0; i<26; i++) chd[i]=-1;
        for(i=0; i<=MAXM; i++) par[i]=-1;
    }

    Node(int _dep, char _c, int _par)
    {
        int i, j;
        dep=_dep; c=_c; par[0]=_par;
        for(i=0; i<26; i++) chd[i]=-1;
        for(i=1; i<=MAXM; i++) par[i]=-1;
    }
};
int cnt;
Node nodes[MAXN+10];
int A[MAXN+10], T=0;

int makeNode(int dep, char c, int par)
{
    int i, j;
    nodes[cnt]=Node(dep, c, par);
    for(i=1; i<=MAXM; i++) nodes[cnt].par[i]=nodes[nodes[cnt].par[i-1]].par[i-1];
    return cnt++;
}

void Init()
{
    T=0;
    A[0]=makeNode(0, '!', -1);
}

void TypeLetter(char c)
{
    int i, j;
    T++;

    int now=A[T-1];
    if(nodes[now].chd[c-'a']==-1) nodes[now].chd[c-'a']=makeNode(nodes[now].dep+1, c, now);
    A[T]=nodes[now].chd[c-'a'];
}

void UndoCommands(int u)
{
    int i, j;
    T++;
    A[T]=A[T-1-u];
}

char GetLetter(int P)
{
    int i, j;

    int now=A[T];
    P=nodes[now].dep-P-1;

    for(i=MAXM; i>=0; i--)
    {
        if(P>=(1<<i))
        {
            now=nodes[now].par[i];
            P-=(1<<i);
        }
    }
    return nodes[now].c;
}

Compilation message

scrivener.cpp: In constructor 'Node::Node()':
scrivener.cpp:18:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
scrivener.cpp: In constructor 'Node::Node(int, char, int)':
scrivener.cpp:26:16: warning: unused variable 'j' [-Wunused-variable]
         int i, j;
                ^
scrivener.cpp: In function 'int makeNode(int, char, int)':
scrivener.cpp:38:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:52:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
scrivener.cpp:52:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
scrivener.cpp: In function 'void UndoCommands(int)':
scrivener.cpp:62:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
scrivener.cpp:62:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:69:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 207820 KB Output is correct
2 Correct 192 ms 207708 KB Output is correct
3 Correct 189 ms 207736 KB Output is correct
4 Correct 191 ms 207736 KB Output is correct
5 Correct 188 ms 207708 KB Output is correct
6 Correct 191 ms 207808 KB Output is correct
7 Correct 189 ms 207868 KB Output is correct
8 Correct 189 ms 207760 KB Output is correct
9 Correct 209 ms 207768 KB Output is correct
10 Correct 189 ms 207736 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 207844 KB Output is correct
2 Correct 190 ms 207868 KB Output is correct
3 Correct 189 ms 207736 KB Output is correct
4 Correct 189 ms 207736 KB Output is correct
5 Correct 189 ms 207752 KB Output is correct
6 Correct 190 ms 207924 KB Output is correct
7 Correct 189 ms 207716 KB Output is correct
8 Correct 189 ms 207796 KB Output is correct
9 Correct 190 ms 208020 KB Output is correct
10 Correct 190 ms 207744 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 207728 KB Output is correct
2 Correct 192 ms 207864 KB Output is correct
3 Correct 191 ms 207836 KB Output is correct
4 Correct 192 ms 207768 KB Output is correct
5 Correct 222 ms 207804 KB Output is correct
6 Correct 192 ms 207836 KB Output is correct
7 Correct 192 ms 207852 KB Output is correct
8 Correct 190 ms 207864 KB Output is correct
9 Correct 191 ms 207872 KB Output is correct
10 Correct 191 ms 207884 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 211384 KB Output is correct
2 Correct 804 ms 212856 KB Output is correct
3 Correct 596 ms 213032 KB Output is correct
4 Correct 582 ms 214736 KB Output is correct
5 Correct 655 ms 214264 KB Output is correct
6 Correct 659 ms 213792 KB Output is correct
7 Correct 670 ms 212504 KB Output is correct
8 Correct 732 ms 212600 KB Output is correct
9 Correct 875 ms 214520 KB Output is correct
10 Correct 410 ms 214648 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 211720 KB Output is correct
2 Correct 850 ms 211740 KB Output is correct
3 Correct 567 ms 212692 KB Output is correct
4 Correct 571 ms 211420 KB Output is correct
5 Correct 650 ms 212820 KB Output is correct
6 Correct 612 ms 211960 KB Output is correct
7 Correct 651 ms 213044 KB Output is correct
8 Correct 753 ms 211800 KB Output is correct
9 Correct 933 ms 211660 KB Output is correct
10 Correct 410 ms 213240 KB Output is correct