| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1341264 | tomdev | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++17 | 0 ms | 0 KiB |
/**
* author: TomDev - Tran Hoang Quan
* created: 2026-03-24 10:55:39
* country: Vietnam - VNM
* ----------------------------------------------------------
* title: IOI 2012 - Scrivener
* source: https://oj.uz/problem/view/IOI12_scrivener
* submission:
* status: WIP
* ----------------------------------------------------------
* tags:
* complexity:
* note:
**/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <utility>
using namespace std;
// --- [ DEBUGGING & LOCAL CONFIG ] ---
#if __has_include("TomDev.h")
#include "TomDev.h"
#define dbg(x,i) cerr << "BreakPoint(" << i << ") -> " << #x << " = " << (x) << '\n'
#else
#define dbg(x,i)
#endif
#define NAH_I_WOULD_WIN 0
// --- [ MACROS ] ---
#define all(x,bonus) (x).begin()+(bonus),(x).end()
#define range(x,st,ed) (x).begin()+(st),(x).begin()+(ed)+1
#define filter(x,bonus) (x).erase(unique((x).begin()+(bonus), (x).end()), (x).end())
#define rall(x,bonus) (x).rbegin(),(x).rend()-(bonus)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fi first
#define se second
#define eb emplace_back
#define sz(x) (int)(x).size()
// --- [ TYPES & ALIASES ] ---
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<long long,long long>;
using pld = pair<long double,long double>;
using pii = pair<int,int>;
using pill = pair<int,long long>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<long long>;
using vvll = vector<vector<long long>>;
using vpii = vector<pair<int,int>>;
using vpill = vector<pair<int,long long>>;
using vpll = vector<pair<long long,long long>>;
void setup(){
if(!fopen("IOI12_scrivener.INP", "r")) return;
freopen("IOI12_scrivener.INP", "r", stdin);
freopen("IOI12_scrivener.OUT", "w", stdout);
}
// ----------------------- [ CONFIG & CONSTANTS ] -----------------------
const int N = 1e6+2;
int up[N][21], h[N], pos[N];
char val[N];
int cur = 0, n = 0;
// ----------------------- [ FUNCTIONS ] -----------------------
void Init();
void TypeLetter(char c){
n++;
pos[n] = n;
val[n] = c;
h[n] = h[cur] + 1;
up[n][0] = cur;
for(int k = 1; k <= 20; k++) up[n][k] = up[up[n][k-1]][k-1];
cur = n;
}
void UndoCommands(int x){
pos[n+1] = pos[n - x];
n++;
cur = pos[n];
}
char GetLetter(int x){
x = h[cur] - x - 1;
int ans = cur;
for(int k = 20; k >= 0; k--){
if(x >> k & 1) ans = up[ans][k];
}
return val[ans];
}
// ----------------------- [ MAIN ] -----------------------
