Submission #1289285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289285		MisterReaper	카멜레온의 사랑 (JOI20_chameleon)	C++20	100 / 100	30 ms	564 KiB

chameleon

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

#ifdef DEBUG
    #include "../debug.h"
#else
    #define debug(...) void(23)
#endif

namespace {

// int variable_example = 1;

std::vector<int> mtc;

}  // namespace

void answer(int a, int b) {
    debug("answer:", a, b);
    if (mtc[a] != -1) {
        assert(mtc[a] == b);
    } else {
        mtc[a] = b;
        mtc[b] = a;
        Answer(a + 1, b + 1);
    }
}

int query(std::vector<int> v) {
    for (auto& i : v) {
        i += 1;
    }
    return Query(v);
}

void Solve(int N) {
    // std::vector<int> p(3);
    // p[0] = 1;
    // p[1] = 2;
    // p[2] = 3;
    // variable_example = Query(p);
    // for (int i = 0; i < N; ++i) {
    //    Answer(i * 2 + 1, i * 2 + 2);
    // }

    std::vector<std::vector<int>> adj(2 * N);

    std::vector<int> col;
    auto dfs = [&](auto&& self, int v) -> void {
        for (auto u : adj[v]) {
            if (col[u] == -1) {
                col[u] = !col[v];
                self(self, u);
            } else {
                assert(col[u] == !col[v]);
            }
        }
    };

    for (int i = 0; i < 2 * N; ++i) {
        col.assign(2 * N, -1);
        std::vector<int> gr[2];
        for (int j = 0; j < i; ++j) {
            if (col[j] == -1) {
                col[j] = 0;
                dfs(dfs, j);
            }
            gr[col[j]].emplace_back(j);
        }
        debug(i);
        debug(gr[0]);
        debug(gr[1]);
        for (int g : {0, 1}) {
            std::vector<int> all = gr[g];
            while (int(adj[i].size()) != 3) {
                auto v = all;
                v.emplace_back(i);
                if (query(v) == int(v.size())) {
                    break;
                }
                v.pop_back();
                while (int(v.size()) > 1) {
                    int n = int(v.size());
                    std::vector<int> vl(v.begin(), v.begin() + n / 2);
                    std::vector<int> vr(v.begin() + n / 2, v.end());
                    vl.emplace_back(i);
                    if (query(vl) != n / 2 + 1) {
                        vl.pop_back();
                        v = vl;
                    } else {
                        v = vr;
                    }
                }
                debug(v[0], i);
                adj[v[0]].emplace_back(i);
                adj[i].emplace_back(v[0]);
                all.erase(std::find(all.begin(), all.end(), v[0]));
            }
        }
    }

    for (int i = 0; i < 2 * N; ++i) {
        debug(i, adj[i]);
    }

    mtc.assign(2 * N, -1);

    for (int i = 0; i < 2 * N; ++i) {
        if (adj[i].size() == 1) {
            int x = adj[i][0];
            answer(i, x);
        }
    }

    std::vector<std::pair<int, int>> err;

    for (int i = 0; i < 2 * N; ++i) {
        if (int(adj[i].size()) == 3) {
            int a = adj[i][0];
            int b = adj[i][1];
            int c = adj[i][2];
            int x = query({i, a, b});
            int y = query({i, a, c});
            int z = query({i, b, c});
            if (x == 1) {
                err.emplace_back(i, c);
            } else if (y == 1) {
                err.emplace_back(i, b);
            } else {
                err.emplace_back(i, a);
            }
        }
    }

    for (auto[x, y] : err) {
        debug(x, y);
        auto itx = std::find(adj[x].begin(), adj[x].end(), y);
        auto ity = std::find(adj[y].begin(), adj[y].end(), x);
        if (itx != adj[x].end()) {
            adj[x].erase(itx);
        }
        if (ity != adj[y].end()) {
            adj[y].erase(ity);
        }
    }

    for (int i = 0; i < 2 * N; ++i) {
        debug(adj[i]);
    }

    for (int i = 0; i < 2 * N; ++i) {
        if (!adj[i].empty()) {
            answer(i, adj[i][0]);
        }
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36