Submission #1289265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289265		MisterReaper	Chameleon's Love (JOI20_chameleon)	C++20	40 / 100	17 ms	448 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) {
        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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36