Submission #172111

#	Time	Username	Problem	Language	Result	Execution time	Memory
172111		arnold518	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	997 ms	216056 KiB

scrivener

#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 (stderr)

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40