Submission #604877

#	Time	Username	Problem	Language	Result	Execution time	Memory
604877		piOOE	Mechanical Doll (IOI18_doll)	C++17	63 / 100	258 ms	15244 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

void create_circuit(int m, vector<int> a) {
    int n = (int) a.size();
    vector<int> c(m + 1, 0), x, y;
    auto solve1 = [](vector<int> a, int n, int m) ->array<vector<int>, 3>{
        vector<int> x, y, c(m + 1);
        c[0] = a[0];
        a.push_back(0);
        function<int(vector<int>)> solve = [&](vector<int> z) -> int {
            if (z.size() == 1) {
                return z[0];
            }
            int last = -((int) x.size() + 1);
            x.push_back(0), y.push_back(0);
            vector<int> L, R;
            for (int i = 0; i < (int) z.size(); ++i) {
                if (i & 1 ^ 1) {
                    L.push_back(z[i]);
                } else {
                    R.push_back(z[i]);
                }
            }
            if (L.size() > R.size()) {
                R.push_back(L.back());
                L.back() = last;
            }
            int ll = solve(L), rr = solve(R);
            x[-last - 1] = ll, y[-last - 1] = rr;
            return last;
        };
        a.erase(a.begin());
        int last = solve(a);
        for (int i = 1; i <= m; ++i) {
            c[i] = last;
        }
        return {c, x, y};
    };
    auto solve2 = [](vector<int> a, int n, int m) ->array<vector<int>, 3>{
        vector<int> x, y, c(m + 1);
        c[0] = a[0];
        a.push_back(0);
        vector<vector<int>> g(m + 1);
        for (int i = 0; i < n; ++i) {
            g[a[i]].push_back(a[i + 1]);
        }
        for (int i = 1; i <= m; ++i) {
            if (!g[i].empty()) {
                function<int(vector<int>)> solve = [&](vector<int> z) -> int {
                    if (z.size() == 1) {
                        return z[0];
                    }
                    int last = -((int) x.size() + 1);
                    x.push_back(0), y.push_back(0);
                    vector<int> L, R;
                    for (int i = 0; i < (int) z.size(); ++i) {
                        if (i & 1 ^ 1) {
                            L.push_back(z[i]);
                        } else {
                            R.push_back(z[i]);
                        }
                    }
                    if (L.size() > R.size()) {
                        R.push_back(L.back());
                        L.back() = last;
                    }
                    int ll = solve(L), rr = solve(R);
                    x[-last - 1] = ll, y[-last - 1] = rr;
                    return last;
                };
                c[i] = solve(g[i]);
            }
        }
        return {c, x, y};
    };
    auto s1 = solve1(a, n, m), s2 = solve2(a, n, m);
    if (s1[2].size() < s2[2].size()) {
        answer(s1[0], s1[1], s1[2]);
    } else {
        answer(s2[0], s2[1], s2[2]);
    }
}

Compilation message (stderr)

doll.cpp: In lambda function:
doll.cpp:21:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   21 |                 if (i & 1 ^ 1) {
      |                     ~~^~~
doll.cpp: In lambda function:
doll.cpp:60:31: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |                         if (i & 1 ^ 1) {
      |                             ~~^~~

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