Submission #1210133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210133		onbert	Mechanical Doll (IOI18_doll)	C++17	100 / 100	62 ms	12584 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5, maxm = 2e5 + 5;
int n, m;
vector<int> a;
int cnt = 0;
int adj[maxn][2];
bool mode[maxn];

int build(int sz, int p) {
    if (sz == 0) return 1;
    else if (sz == 1 && p == -1) return -1;
    int u = ++cnt;
    int val = (1 << p);
    adj[u][0] = build(max(sz - val, (int)0), p-1);
    adj[u][1] = build(min(val, sz), p-1);
    return u;
}

void create_circuit(int M, vector<int> A) {
    m = M, a = A;
    n = a.size();
    n++;
    a.push_back(0);
    build(n, log2(n - 1));
    for (int i=0;i<n;i++) {
        int u = 1;
        while (true) {
            int v = adj[u][mode[u]];
            mode[u] = !mode[u];
            if (v == -1) {
                adj[u][!mode[u]] = -a[i];
                break;
            }
            u = v;
        }
    }
    vector<int> C(m+1, -1), X(cnt), Y(cnt);
    for (int i=1;i<=cnt;i++) X[i-1] = -adj[i][0], Y[i-1] = -adj[i][1];
    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