Submission #396313

#	Time	Username	Problem	Language	Result	Execution time	Memory
396313		12tqian	Mechanical Doll (IOI18_doll)	C++17	100 / 100	386 ms	22696 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;

using namespace std;

void create_circuit(int m, vi a) { // example circuit
    // m is the number of triggers
    // n is the length of the sequence
    int n = sz(a);
    vi c(m + 1);
    if (n == 1) {
        f1r(i, 1, m + 1) {
            c[i] = 0;
        }
        c[0] = a[0];
        answer(c, vi(), vi());
        return;
    }
    // root switch at -1
    f1r(i, 1, m + 1) {
        c[i] = -1; // connect to the root
    }
    c[0] = a[0];
    a.erase(a.begin()); // erase first element
    a.pb(0); // add the beginning again 
    // now from the root, we go to each number in some order
    // we need n exits
    // i -> 2 * i, 2 * i + 1
    int d = 0;
    while ((1 << d) < n) d++;
    int sz = (1 << d); // this is the bottom row
    // leaf nodes are the exits
    int excess = sz - n; // stuff not used on bottom row
        
    vi dead(2 * sz);
    vi state(2 * sz);
    
    f0r(i, excess) {
        dead[sz + i] = 1;
    }
    
    function<void(int)> gather = [&](int u) {
        if (u >= sz) return;
        gather(2 * u);
        gather(2 * u + 1);
        dead[u] = (dead[2 * u] & dead[2 * u + 1]);
    }; gather(1); 

    vi ord;

    f0r(i, n) { // go through each of the nodes
        int bot = -1;
        function<bool(int)> go = [&](int u) -> bool {
            if (u >= sz) {
                bot = u;
                return dead[u];
            } else {
                if (state[u] == 0) {
                    state[u] ^= 1;
                    return go(2 * u); 
                } else {
                    state[u] ^= 1;
                    return go(2 * u + 1);
                }
            }
        }; while (go(1)) {}
        ord.pb(bot); 
    }
    map<int, int> xdest, ydest;
    f0r(i, sz(ord)) {
        int u = ord[i];
        int p = u / 2;
        if (2 * p == u) { 
            xdest[p] = a[i]; 
        } else {
            ydest[p] = a[i];
        }
    }
    vi used;
    function<void(int)> dfs = [&](int u) {
        if (dead[u]) {
            return;
        }
        if (u >= sz) {
            return;
        } else {
            used.pb(u);
            dfs(2 * u);
            dfs(2 * u + 1);
        }
    };
    dfs(1);
    // cout << sz(used) << endl;
    sort(all(used));
    auto get_pos = [&](int x) -> int { return lower_bound(all(used), x) - used.begin(); };
    int s = sz(used);
    vi x(s);    
    vi y(s);
    each(v, used) {
        int i = get_pos(v);
        if (2 * v < sz) {
            if (!dead[2 * v]) {
                int to = get_pos(2 * v);
                x[i] = -(to + 1);
            } else {
                x[i] = -1;
            }
            if (!dead[2 * v + 1]) {
                int to = get_pos(2 * v + 1);
                y[i] = -(to + 1);
            } else {
                y[i] = -1;
            }
        } else {
            if (!dead[2 * v]) {
                x[i] = xdest[v];
            } else {
                x[i] = -1;
            }
            if (!dead[2 * v + 1]) {
                y[i] = ydest[v];
            } else {
                y[i] = -1;
            }
        }
    }
    answer(c, x, y);
    auto output = [&](vi v) { each(x, v) cout << x << " "; cout << endl; };
#ifndef LOCAL
    // output(a);
    // output(c);
    // output(x);
    // output(y);
#endif
    return;
}

/**
 * n + log2 switches for full credit
 * 1e5 triggers, 2e5 length sequence
 * P  is like 20 * n, which is like log2(m) * n ish?
 * general observations
     * from a trigger you go to same switch every time
     * so you have a binary choice of next switch
     * 2n switches is easy
     * you can choose specifically which switches to ignore
     * if you make it into like sets of 2^k, and then just redirect them back to the beginning
     * the idea is you can figure out where to direct the things, i see
 * subtask 1
     * make a ordered cycle
 * subtask 2
     * if you go to some place twice, use the switch appropriately
 * subtask 3
     * you can just do similarly to task 2
 * subtask 4
     * 
 * subtask 5
     * 
 * subtask 6
     *
 */

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:150:10: warning: variable 'output' set but not used [-Wunused-but-set-variable]
  150 |     auto output = [&](vi v) { each(x, v) cout << x << " "; cout << endl; };
      |          ^~~~~~

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