Submission #234499

#	Time	Username	Problem	Language	Result	Execution time	Memory
234499		nafis_shifat	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	446 ms	140024 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e6+6;


int tree[mxn][26];
int pos[mxn];
int pt=0;
int idx=0;
int dp[20][mxn]={};

int con[mxn];
int len[mxn];
void Init() {
    len[0]=0;
    pos[0]=0;
}
int climb(int p,int k) {
    
    for(int i=0;i<20;i++) {
        if(k>>i & 1)p=dp[i][p];
    }
    return p;
}

void TypeLetter(char L) {
    L-='a';
    int lp=pos[pt];
    if(tree[lp][L]) {
        pos[++pt]=tree[lp][L];
    } else {
        tree[lp][L]=++idx;
        pos[++pt]=tree[lp][L];
        con[idx]=L;
        dp[0][idx]=lp;
        len[idx]=len[lp]+1;
        for(int i=1;i<20;i++) {
            dp[i][idx]=dp[i-1][dp[i-1][idx]];
        }
    }
}
void UndoCommands(int u) {
    pos[pt+1]=pos[pt - u];
    pt++;
}
char GetLetter(int p) {
    p++;
	int c=len[pos[pt]];
	char r='a' + (con[climb(pos[pt],c-p)]);
	return r;
}

Compilation message (stderr)

scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:29:18: warning: array subscript has type 'char' [-Wchar-subscripts]
     if(tree[lp][L]) {
                  ^
scrivener.cpp:30:29: warning: array subscript has type 'char' [-Wchar-subscripts]
         pos[++pt]=tree[lp][L];
                             ^
scrivener.cpp:32:19: warning: array subscript has type 'char' [-Wchar-subscripts]
         tree[lp][L]=++idx;
                   ^
scrivener.cpp:33:29: warning: array subscript has type 'char' [-Wchar-subscripts]
         pos[++pt]=tree[lp][L];
                             ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40