Submission #422001

#	Time	Username	Problem	Language	Result	Execution time	Memory
422001		Lobo	Crayfish scrivener (IOI12_scrivener)	C++17	5 / 100	162 ms	26240 KiB

scrivener

#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = 1e18+10;
const int INFii = 1e9+10;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back

#define maxn 110000
#define log 25
//LEMBRAR DE MUDAR

ii n, tmp, p[maxn][log], t[maxn], h[maxn];
char c[maxn];

void TypeLetter(char L) {
    n++;
    tmp++;
    t[tmp] = n;
    c[n] = L;

    p[n][0] = t[tmp-1];
    h[n] = h[t[tmp-1]] + 1;

    for(ii i = 1; i <= log; i++) {
        p[n][i] = p[p[n][i-1]][i-1];
    }

    //cout << L << " " << n << " " << tmp << " -> " << h[n] << endl;
}

void UndoCommands(int U) {
    tmp++;
    t[tmp] = t[tmp-U-1];
}

char GetLetter(int P) {
    ii u = t[tmp];
    P = h[tmp]-P-1;

    for(ii i = log; i >= 0; i--) {
        if(P-(1<<i) >= 0) {
            P-= (1<<i);
            u = p[u][i];
        }
    }

    return c[u];
}

void Init() {
}

Compilation message (stderr)

scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:33:17: warning: iteration 24 invokes undefined behavior [-Waggressive-loop-optimizations]
   33 |         p[n][i] = p[p[n][i-1]][i-1];
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~
scrivener.cpp:32:21: note: within this loop
   32 |     for(ii i = 1; i <= log; i++) {
      |                     ^

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