Submission #470575

#	Time	Username	Problem	Language	Result	Execution time	Memory
470575		Killer2501	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	523 ms	69976 KiB

scrivener

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 2e6 + 5;
const int M = 1300;
const ll mod = 1e9 + 7;
int n, m, t, cur, node, cnt, a[N], nchar, p[N][21], h[N];
char c[N];
void Init()
{
}
void TypeLetter(char L)
{
    ++nchar;
    h[nchar] = h[cur] + 1;
    p[nchar][0] = cur;
    ++cnt;
    cur = nchar;
    a[cnt] = nchar;
    c[nchar] = L;
    for(int i = 1; i <= 20; i ++)p[nchar][i] = p[p[nchar][i-1]][i-1];
}
void UndoCommands(int U)
{
    cur = a[cnt - U];
    ++cnt;
    a[cnt] = cur;
}
char GetLetter(int P)
{
    int dis = h[cur] - P - 1;
    int u = cur;
    for(int i = 20; i >= 0; i --)
        if((dis >> i) & 1)u = p[u][i];
    return c[u];
}

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