Submission #1341268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1341268		tomdev	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	281 ms	90440 KiB

scrivener

/**
 *    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 ] -----------------------

Compilation message (stderr)

scrivener.cpp: In function 'void setup()':
scrivener.cpp:62:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     freopen("IOI12_scrivener.INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scrivener.cpp:63:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     freopen("IOI12_scrivener.OUT", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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