oj.uz

Submission #172111

# Submission time Handle Problem Language Result Execution time Memory
172111 2019-12-31T07:29:15 Z arnold518 Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 997 ms 216056 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<=30; 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;
            ^
scrivener.cpp: In constructor 'Node::Node()':
scrivener.cpp:21:36: warning: iteration 21 invokes undefined behavior [-Waggressive-loop-optimizations]
         for(i=0; i<=30; i++) par[i]=-1;
                              ~~~~~~^~~
scrivener.cpp:21:19: note: within this loop
         for(i=0; i<=30; i++) par[i]=-1;
                  ~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 207736 KB Output is correct
2 Correct 211 ms 207736 KB Output is correct
3 Correct 207 ms 207740 KB Output is correct
4 Correct 205 ms 207836 KB Output is correct
5 Correct 205 ms 207804 KB Output is correct
6 Correct 210 ms 207764 KB Output is correct
7 Correct 210 ms 207932 KB Output is correct
8 Correct 209 ms 207924 KB Output is correct
9 Correct 206 ms 207864 KB Output is correct
10 Correct 208 ms 207736 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 207812 KB Output is correct
2 Correct 211 ms 207796 KB Output is correct
3 Correct 207 ms 207736 KB Output is correct
4 Correct 207 ms 207844 KB Output is correct
5 Correct 208 ms 207752 KB Output is correct
6 Correct 206 ms 207804 KB Output is correct
7 Correct 205 ms 207736 KB Output is correct
8 Correct 214 ms 207836 KB Output is correct
9 Correct 217 ms 207780 KB Output is correct
10 Correct 223 ms 207864 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 207736 KB Output is correct
2 Correct 213 ms 207892 KB Output is correct
3 Correct 207 ms 207864 KB Output is correct
4 Correct 212 ms 207864 KB Output is correct
5 Correct 207 ms 207980 KB Output is correct
6 Correct 207 ms 207864 KB Output is correct
7 Correct 209 ms 207788 KB Output is correct
8 Correct 210 ms 207896 KB Output is correct
9 Correct 221 ms 207924 KB Output is correct
10 Correct 211 ms 207864 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 211260 KB Output is correct
2 Correct 864 ms 213496 KB Output is correct
3 Correct 674 ms 213752 KB Output is correct
4 Correct 747 ms 213824 KB Output is correct
5 Correct 677 ms 214008 KB Output is correct
6 Correct 697 ms 214424 KB Output is correct
7 Correct 704 ms 212120 KB Output is correct
8 Correct 810 ms 212472 KB Output is correct
9 Correct 871 ms 214264 KB Output is correct
10 Correct 436 ms 214264 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 211668 KB Output is correct
2 Correct 926 ms 211296 KB Output is correct
3 Correct 584 ms 211148 KB Output is correct
4 Correct 589 ms 211064 KB Output is correct
5 Correct 655 ms 211576 KB Output is correct
6 Correct 683 ms 211684 KB Output is correct
7 Correct 640 ms 211660 KB Output is correct
8 Correct 806 ms 211480 KB Output is correct
9 Correct 997 ms 211280 KB Output is correct
10 Correct 436 ms 216056 KB Output is correct