제출 #702352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702352		Ronin13	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	100 / 100	433 ms	67180 KiB

scrivener

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

int cnt = 1;
const int nmax = 1000001;
int a[nmax][20];
char c[nmax];
int depth[nmax];
int last[nmax];
int cur = 0;

void Init() {

}

void TypeLetter(char L) {
    a[cnt][0] = last[cur];
    depth[cnt] = depth[last[cur]] + 1;
    for(int j = 1; j < 20; j++)
        a[cnt][j] = a[a[cnt][j - 1]][j - 1];
    last[cur + 1] = cnt;
    c[cnt] = L;
    cnt++;
    cur++;
}

void UndoCommands(int U) {
    cur++;
    last[cur] = last[cur - U - 1];
   // cout << depth[last[cur]];
}

char GetLetter(int P) {
    int x = depth[last[cur]];
   // cout << x << ' ';
    int o = x - P - 1;
    int cc = last[cur];
    while(o){
        int t = log2(o);
        cc = a[cc][t];
        o -= (1 << t);
    }
    return c[cc];
}

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