Submission #1255649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255649		Art	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	34 / 100	1096 ms	90520 KiB

scrivener

// copy from iancunha, just test time elapsed
#include <bits/stdc++.h>
//#define int int64_t
#define f first
#define s second
#define opt1 ios_base::sync_with_stdio(false)
#define opt2 cin.tie(NULL)
#define optimize opt1; opt2
#define pb push_back
#define sz(v) (int)v.size()
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
typedef pair<ii, ii> i4;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<i3> vi3;
typedef vector<i4> vi4;
const int inf = 0x6f6f6f6f;
const int MAX = 1000005;
const int LOG = 21;
const int mod = 1e9+7;

int st[MAX][LOG];
int curr = 0, a[MAX] = {-1}, R[MAX], T[MAX];
string str = "";

void Init () {
    st[0][0] = 0;
    a[0] = -1;
}

void TypeLetter (char L) {
    str.pb(L);
    curr++;
    a[curr] = a[curr-1]+1;
    T[curr] = T[curr-1]+1;
    st[curr][0] = curr-1;
    for (int bit = 1; bit < LOG; bit++)
        st[curr][bit] = st[st[curr][bit-1]][bit-1];
}

void UndoCommands (int U) {
    str.pb('R');
    curr++;
    R[curr] = U;
    a[curr] = a[curr-U-1]+1;
    T[curr] = T[curr-U-1];
    st[curr][0] = curr-U-1;
    for (int bit = 1; bit < LOG; bit++)
        st[curr][bit] = st[st[curr][bit-1]][bit-1];
}

int Lift (int b, int val) {
    for (int bit = LOG-1; bit >= 0; bit--)
        if (T[st[b][bit]] >= val)
            b = st[b][bit];
    return b;
}

char GetLetter (int P) {
    P = Lift(curr, P+1);
    return str[P-1];    
}

/*
    abd2ue15c2
a:  0121233234
T:  0120121121
*/

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