Submission #805077

#	Time	Username	Problem	Language	Result	Execution time	Memory
805077		Boomyday	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	633 ms	188660 KiB

scrivener

//
// Created by adavy on 2/11/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!

const int lg = 24;





struct Node{
    char c;
    int dp;
    vector<Node*> par;

    Node(char c) {
        dp = 0;
        par.rsz(lg);
        this->c = c;
        par[0] = this;
        for(int j=1;j<lg;++j){
            par[j] = par[j-1]->par[j-1];
        }
    }
    Node(char c, Node* parent){
        par.rsz(lg);
        this-> dp = parent->dp+1;
        this->c = c;
        par[0] = parent;
        for(int j=1;j<lg;++j){
            par[j] = par[j-1]->par[j-1];
        }
    }

    char lift(int n){
        Node* cur = this;
        F0R(j,lg) if (n&(1<<j)) cur = cur->par[j];
        return cur->c;
    }

};
vector<Node*> ops;
int cur;
void Init() {


    Node* nd = new Node('$');
    cur = 0;
    ops.pb(nd);
}

void TypeLetter(char L) {
    Node* nd = new Node(L, ops[cur]);
    cur++;
    ops.pb(nd);

}

void UndoCommands(int U) {

    Node* nd = ops[cur-U];
    ops.pb(nd);
    cur++;
}

char GetLetter(int P) {
    //cout << "cur" << ops[cur]->dp-1-P << endl;
    return ops[cur]->lift( ops[cur]->dp-1-P);
}

/*
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16


int tmp;
int main() {
    Init();

    int cmd_num;
    tmp = scanf("%d", &cmd_num);
    assert(tmp == 1);

    int i;
    for (i = 0; i < cmd_num; i++) {
        char cmd;
        tmp = scanf(" %c", &cmd);
        assert(tmp == 1);
        if (cmd == 'T') {
            char letter;
            tmp = scanf(" %c", &letter);
            assert(tmp == 1);
            TypeLetter(letter);
        }
        else if (cmd == 'U') {
            int number;
            tmp = scanf("%d", &number);
            assert(tmp == 1);
            UndoCommands(number);
        }
        else if (cmd == 'P') {
            int index;
            char letter;
            tmp = scanf("%d", &index);
            assert(tmp == 1);
            letter = GetLetter(index);
            printf("%c\n", letter);
        }
    }

    puts("Let's test for cheating!!");

    return 0;

}
*/

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