Submission #1191257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191257		MatteoArcari	Mechanical Doll (IOI18_doll)	C++20	53 / 100	101 ms	40208 KiB

doll

#include <bits/stdc++.h>
using namespace std;

void answer(vector<int> c, vector<int> x, vector<int> y);

void create_circuit(int m, vector<int> a) {
    int n = a.size();
    vector<int> c(m + 1), x, y;
    vector<vector<int>> cnt(m + 1);
    cnt[0].push_back(a[0]);
    a.push_back(0);
    for (int i = 0; i < n; i++) {
        cnt[a[i]].push_back(a[i + 1]);
    }

    c[0] = a[0];

    queue<int> s;
    vector<vector<int>> to;

    for (int i = 1; i <= m; i++) {
        if (cnt[i].size() == 0) {
            c[i] = 0;
            continue;
        }
        if (cnt[i].size() == 1) {
            c[i] = cnt[i][0];
            continue;
        }

        bool flag = true;
        for (int j = 0; j < cnt[i].size() && flag; j++) {
            if (cnt[i][j] != cnt[i][0]) flag = 0;
        }
        if (flag) {
            c[i] = cnt[i][0];
            continue;
        }

        int j = x.size() + 1;
        c[i] = -j;
        s.push(j);
        x.push_back(-j);
        y.push_back(-j);
        to.push_back(cnt[i]);
    }

    while (!s.empty()) {
        int j = s.front();
        s.pop();

        if (to[j - 1].size() == 2) {
            x[j - 1] = to[j - 1][0];
            y[j - 1] = to[j - 1][1];
            continue;
        }

        vector<int> _a, _b;
        for (int i = 0; i < to[j - 1].size(); i++) {
            if (i & 1) _b.push_back(to[j - 1][i]);
            else _a.push_back(to[j - 1][i]);
        }

        if (_a.size() > _b.size()) {
            _b.push_back(_a.back());
            _a.pop_back();
            _a.push_back(-j);
        }

        bool flagA = true;
        for (int i = 0; i < _a.size() && flagA; i++) {
            if (_a[i] != _a[0]) flagA = 0;
        }
        bool flagB = true;
        for (int i = 0; i < _b.size() && flagB; i++) {
            if (_b[i] != _b[0]) flagB = 0;
        }

        if (!flagA || !flagB) {
            int k = x.size() + 1;
            x[j - 1] = -k;
            x.push_back(-k);
            y.push_back(-k);
            to.push_back(_a);
            s.push(k);
        } else {
            x[j - 1] = _a[0];
        }

        if (!flagA || !flagB) {
            int k = x.size() + 1;
            y[j - 1] = -k;
            x.push_back(-k);
            y.push_back(-k);
            to.push_back(_b);
            s.push(k);
        } else {
            y[j - 1] = _b[0];
        }
    }

    if (x.size() > 2 * n) exit(1);
    answer(c, x, y);
}

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