Submission #1289274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289274		MisterReaper	Chameleon's Love (JOI20_chameleon)	C++20	0 / 100	29 ms	472 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);

    // for (int i = 0; i < 2 * N; ++i) {
    //     for (int j = i + 1; j < 2 * N; ++j) {
    //         int x = query({i, j});
    //         if (x == 1) {
    //             debug(i, j);
    //             adj[i].emplace_back(j);
    //             adj[j].emplace_back(i);
    //         }
    //     }
    // }

    for (int i = 0; i < 2 * N; ++i) {
        std::vector<int> all(N);
        std::iota(all.begin(), all.end(), (i < N ? N : 0));
        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;
                }
            }
            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];
            auto it = std::find(adj[x].begin(), adj[x].end(), i);
            adj[x].clear();
            adj[i].clear();
            answer(i, x);
        }
    }

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

    for (int i = 0; i < 2 * N; ++i) {
        if (mtc[i] == -1) {
            for (auto j : adj[i]) {
                bool bad = true;
                for (auto k : adj[j]) {
                    if (k == i) {
                        continue;
                    }
                    std::vector<int> vec = {i, j, k};
                    debug(i, j, k, query(vec));
                    if (query(vec) == 1) {
                        bad = false;
                    }
                }
                if (bad) {
                    err.emplace_back(i, j);
                }
            }
        }
    }

    for (auto[x, y] : err) {
        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: 0 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36