Submission #928519

#	Time	Username	Problem	Language	Result	Execution time	Memory
928519		GrindMachine	Mechanical Doll (IOI18_doll)	C++17	100 / 100	100 ms	9444 KiB

doll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

design idea:
build a chain of length = k, k is the smallest num s.t 2^k >= n
each of them are connected to each other by Y edges
if the root is visited x times, then:
1st subtree visited x/2 times,
2nd subtree visited x/4 times,
3rd subtree visited x/8 times,
...

decompose n into pows of 2
for each pow of 2, build a binary tree in the corresponding position on the chain
eg: a binary tree of size 2^(k-1) goes on the first position in the chain, size 2^(k-2) goes on the 2nd position etc

there are exactly n binary tree nodes in total
each node corresponds to the state after visiting the first i triggers
the state for each node can be found by simulating the ball from the root
if cnt no.of vals have been visited before reaching a leaf node (including the current node), then the current node is a[cnt-1], so it has to be connected to a[cnt]
if cnt == n, then it means that this node is the last node
so connect it to the root of the chain (after this, no leaf node is every encountered, and the ball leaves the Y exit of the last node on the chain to reach 0)
when the ball leaves by the Y exit of the last node on the chain, all switches would have state X
we also use <= n+log2(n) nodes (~n for the bin.tree, ~log2(n) for the chain)
so the construction is valid

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "doll.h"

void create_circuit(int m, std::vector<int> a) {
    // int N = A.size();
    // std::vector<int> C(M + 1);
    // C[0] = -1;
    // for (int i = 1; i <= M; ++i) {
    //     C[i] = 1;
    // }
    // std::vector<int> X(N), Y(N);
    // for (int k = 0; k < N; ++k) {
    //     X[k] = Y[k] = A[k];
    // }
    // answer(C, X, Y);

    int n = sz(a);
    a.pb(0);
    vector<int> b(m+1);
    b[0] = a[0];

    vector<int> sx(1), sy(1), leaf(1), flipped(1);

    int siz = 1;
    while(siz <= n) siz <<= 1;
    int chain_siz = __lg(siz);

    int root = 1;

    rep1(i,m){
        b[i] = -root;
    }
    b[0] = a[0];

    rep1(i,chain_siz){
        sx.pb(0), sy.pb(0);
    }
    rep1(i,chain_siz-1){
        sx[root-1+i] = -root;
        sy[root-1+i] = -(root+i);
    }

    sx[root-1+chain_siz] = -root;
    sy[root-1+chain_siz] = 0;

    rev(bit,chain_siz-1,0){
        if(!(n&(1<<bit))) conts;
        if(!bit){
            while(sz(leaf) < sz(sx)){
                leaf.pb(0);
            }
            leaf[root-1+chain_siz] = 1;
            conts;
        }

        // build bin tree, depth = bit-1
        int pos_on_chain = root-1+chain_siz-bit;
        int ptr = sz(sx);
        sx.pb(-root), sy.pb(-root);
        sx[pos_on_chain] = -ptr;
        queue<pii> q;
        q.push({ptr,0});

        while(!q.empty()){
            auto [u,d] = q.front();
            q.pop();

            if(d >= bit-1){
                while(sz(leaf) < sz(sx)){
                    leaf.pb(0);
                }
                leaf[u] = 1;
                conts;
            }

            sx[u] = -sz(sx);
            sy[u] = -(sz(sx)+1);

            sx.pb(-root), sy.pb(-root);
            sx.pb(-root), sy.pb(-root);

            q.push({-sx[u],d+1});
            q.push({-sy[u],d+1});
        }
    }

    while(sz(flipped) < sz(sx)){
        flipped.pb(0);
    }

    int ptr = root;
    int cnt = 0;

    while(true){
        if(leaf[ptr]){
            cnt++;
            if(cnt == n) break;

            flipped[ptr] ^= 1;
            int nxt = a[cnt];

            if(flipped[ptr]){
                sx[ptr] = nxt;
            }
            else{
                sy[ptr] = nxt;
            }

            ptr = root;
        }
        else{
            flipped[ptr] ^= 1;
            if(flipped[ptr]){
                ptr = -sx[ptr];
            }
            else{
                ptr = -sy[ptr];
            }
        }
    }

    sx.erase(sx.begin());
    sy.erase(sy.begin());
    int mx_allowed = n+__lg(n-1)+1;
    assert(sz(sx) <= mx_allowed);
    answer(b,sx,sy);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56