Submission #604864

#	Time	Username	Problem	Language	Result	Execution time	Memory
604864		piOOE	자동 인형 (IOI18_doll)	C++17	63 / 100	176 ms	13384 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;
    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]);
    }
    if (n == 16) {
        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;
        }
    }
    else {
        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]);
            }
        }
    }
    answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In lambda function:
doll.cpp:24:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   24 |                 if (i & 1 ^ 1) {
      |                     ~~^~~
doll.cpp: In lambda function:
doll.cpp:55:31: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   55 |                         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