Submission #571930

#	Time	Username	Problem	Language	Result	Execution time	Memory
571930		elazarkoren	Mechanical Doll (IOI18_doll)	C++17	100 / 100	155 ms	22108 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;

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) {
            right_son = 1;
            a--;
            if (a > 0) {
                left_son = 1;
                a--;
            }
            return;
        }
        y->First(a);
        if (a > 0) x->First(a);
    }
    bool Delete() {
        if (!x) {
            return !left_son && !right_son;
        }
        if (y->Delete()) {
            delete y;
            right_son = 0;
            y = 0;
        }
        if (x->Delete()) {
            delete x;
            left_son = 0;
            x = 0;
        }
        sz = (x ? x->sz : 1) + (y ? y->sz : 1);
        return !left_son && !right_son;
    }
    bool Add(int a) {
        state = !state;
        if (state) {
            if (!x) {
                if (left_son <= 0) {
                    left_son = -1;
                    return false;
                }
                left_son = a;
                return true;
            }
            return x->Add(a);
        }
        else {
            if (!y) {
                if (right_son <= 0) {
                    right_son = -1;
                    return false;
                }
                right_son = a;
                return true;
            }
            return y->Add(a);
        }
    }
    int Create() {
        int node = X.size();
        X.push_back(-1), Y.push_back(-1);
        if (!x) X[node] = left_son;
        else {
            int a = x->Create();
            X[node] = a;
        }
        if (!y) Y[node] = right_son;
        else {
            int 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 = n; i < tree.sz; i++) tree.Add(-1);
    for (int i = 0; i < n; i++) {
        while (!tree.Add(v[i]));
    }
//    tree.Add(v.back());
    tree.Create();
    return -1;
}

void create_circuit(int m, std::vector<int> a) {
    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

//1 20
//1 1 1 1 1

Compilation message (stderr)

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

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