Submission #696704

#	Time	Username	Problem	Language	Result	Execution time	Memory
696704		sharaelong	Mechanical Doll (IOI18_doll)	C++17	100 / 100	115 ms	11400 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int rev(int x, int sz) {
    int k = 31 - __builtin_clz(sz);
    int ret = 0;
    for (int i=0; i<k; ++i) ret |= (1 << (k-1-i)) * ((x & (1 << i)) > 0);
    // cout << x << ' ' << sz << ' ' << ret << endl;
    return ret;
}

const int INF = 1e9;

int switch_cnt = 0;
vector<int> c, x, y;

int solve(int cnt, int lev) {
    // cout << l << ' ' << r << ' ' << lev << endl;
    int root = -switch_cnt-1;
    switch_cnt++;
    if (lev == 1) {
        x.push_back((cnt == 1 ? -1 : INF));
        y.push_back(INF);
        return root;
    }
    
    if (cnt > (1 << (lev-1))) {
        x.push_back(0);
        y.push_back(0);
        x[-root-1] = solve(cnt-(1<<(lev-1)), lev-1);
        y[-root-1] = solve(1<<(lev-1), lev-1);
    } else {
        x.push_back(-1);
        y.push_back(0);
        y[-root-1] = solve(cnt, lev-1);
    }
    return root;
}

void create_circuit(int m, vector<int> A) {
    int n = A.size();
    A.push_back(0);
    c.resize(m+1, -1);

    int lev = 0;
    while (n+1 > (1 << lev)) lev++;
    solve(n+1, lev);

    // for (int i: c) cout << i << ' ';
    // cout << endl;
    // for (int i: x) cout << i << ' ';
    // cout << endl;
    // for (int i: y) cout << i << ' ';
    // cout << endl;

    int curr = -1;
    int allocate_cnt = 0;
    vector<bool> state(x.size(), 0);
    while (curr != 0) {
        if (curr >= 0) curr = c[curr];
        else {
            int& nxt = (state[-curr-1] ? y[-curr-1] : x[-curr-1]);
            if (nxt == INF) {
                nxt = A[allocate_cnt++];
            }
            state[-curr-1] = !state[-curr-1];
            curr = nxt;
        }
        // cout << curr << endl;
    }
    
    answer(c, x, y);
}

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