Submission #571914

#	Time	Username	Problem	Language	Result	Execution time	Memory
571914		elazarkoren	Mechanical Doll (IOI18_doll)	C++17	10 / 100	4 ms	5084 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_M = 1e5 + 5;
const int MAX_N = 1e6;

vi graph[MAX_M];

int sz = 0, wait = 0;
vi X, Y;

struct Node {
    Node *x = 0, *y = 0;
    bool state = false;
    int left_son = 0, right_son = 0;
    int sz = 2;
    Node(int d) {
        if (!d) {
            return;
        }
        x = new Node(d - 1);
        y = new Node(d - 1);
        left_son = 1, right_son = 1;
        sz = x->sz + y->sz;
    }
    void First(int &a) {
        if (!x) {
            left_son = 1;
            a--;
            if (a > 0) {
                right_son = 1;
                a--;
            }
            return;
        }
        x->First(a);
        if (a > 0) y->First(a);
    }
    bool Delete() {
        if (!x) {
            return !left_son && !right_son;
        }
        if (x->Delete()) {
            delete x;
            left_son = 0;
            x = 0;
        }
        if (y->Delete()) {
            delete y;
            right_son = 0;
            y = 0;
        }
        sz = (x ? x->sz : 0) + (y ? y->sz : 0);
        return !left_son && !right_son;
    }
    void Add(int a) {
        if (!x) {
            if (!state) left_son = a;
            else right_son = a;
            state = !state;
            return;
        }
        if (!state) x->Add(a);
        else y->Add(a);
        state = !state;
    }
    int Create() {
        int node = X.size();
        X.push_back(-1), Y.push_back(-1);
        if (!x) {
            X[node] = left_son;
            Y[node] = right_son;
        } else {
            int a = x->Create();
            X[node] = a;
            a = y->Create();
            Y[node] = a;
        }
        node = -node - 1;
        return node;
    }
};

int Solve(vi &v) {
    int n = v.size();
    int bit = 0;
    for (int a = 1; a < n; bit++, a <<= 1);
    bit--;
    Node tree(bit);
    tree.First(n);
    n = v.size();
    tree.Delete();
    for (int i = 0; i < n - 1; i++) {
        tree.Add(v[i]);
    }
    for (int i = n; i < tree.sz; i++) tree.Add(-1);
    tree.Add(v.back());
    tree.Create();
    return -1;
}

void create_circuit(int m, std::vector<int> a) {
    for (int i = 0; i <= m; i++) graph[i].clear();
    X.clear(), Y.clear();
    int n = a.size();
    a.push_back(0);
    int t = a[0];
    a.erase(a.begin());
    if (a.size() == 1 || a.empty()) {
        vi c(m + 1, 0);
        c[0] = t;
        answer(c, X, Y);
        return;
    }
    Solve(a);
    vi c(m + 1, -1);
    c[0] = t;
    answer(c, X, Y);
}
//5 14
//1 2 3 3 2 5 1 1 2 1 4 3 4 3

//1 7
//1 1 1 1 1 1 1

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:116:9: warning: unused variable 'n' [-Wunused-variable]
  116 |     int n = a.size();
      |         ^

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