제출 #1289258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289258		MisterReaper	카멜레온의 사랑 (JOI20_chameleon)	C++20	0 / 100	17 ms	456 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) {
    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].erase(it);
            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) {
        adj[x].erase(std::find(adj[x].begin(), adj[x].end(), y));
        adj[y].erase(std::find(adj[y].begin(), adj[y].end(), x));
    }

    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