Submission #373643

#	Time	Username	Problem	Language	Result	Execution time	Memory
373643		KoD	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	64 ms	768 KiB

chameleon

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

template <class T>
using Vec = std::vector<T>;

template <class F>
struct RecLambda: private F {
    explicit RecLambda(F &&f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

void Solve(int N) {
    Vec<int> color(2 * N + 1);
    Vec<Vec<int>> graph(2 * N + 1);

    const auto difference = [&](const int src, Vec<int> vec) {
        vec.push_back(src);
        return (int) vec.size() - Query(vec);
    };

    const auto enum_edges = RecLambda([&](const auto enum_edges, const int src, Vec<int> partner, int dif) -> int {
        if (graph[src].size() == 3) {
            return 0;
        }
        if (dif == -1) {
            dif = difference(src, partner);
        }
        if (dif == 0) {
            return 0;
        }
        if (partner.size() == 1) {
            return partner.front();
        }
        const auto mid = (int) partner.size() / 2;
        Vec<int> left(partner.begin(), partner.begin() + mid);
        Vec<int> right(partner.begin() + mid, partner.end());
        const auto left_dif = difference(src, left);
        if (left_dif == 0) {
            return enum_edges(src, right, dif);
        }
        else {
            return enum_edges(src, left, left_dif);
        }
    });

    const auto split = RecLambda([&](const auto split, const int u, const int c) -> void {
        if (color[u] != 0) {
            return;
        }
        color[u] = c;
        for (const auto v: graph[u]) {
            split(v, -c);
        }
    });

    for (int src = 1; src <= 2 * N; ++src) {
        Vec<int> v1, v2;
        for (int v = 1; v < src; ++v) {
            bool ok = true;
            for (const auto x: graph[src]) {
                if (x == v) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                (color[v] == 1 ? v1 : v2).push_back(v);
            }
        }
        while (true) {
            const auto dst = enum_edges(src, v1, -1);
            if (dst == 0) {
                break;
            }
            v1.erase(std::lower_bound(v1.begin(), v1.end(), dst));
            graph[src].push_back(dst);
            graph[dst].push_back(src);
        }
        while (true) {
            const auto dst = enum_edges(src, v2, -1);
            if (dst == 0) {
                break;
            }
            v2.erase(std::lower_bound(v2.begin(), v2.end(), dst));
            graph[src].push_back(dst);
            graph[dst].push_back(src);
        }
        std::fill(color.begin(), color.end(), 0);
        for (int v = 1; v <= src; ++v) {
            if (color[v] == 0) {
                split(v, 1);
            }
        }
    }

    std::set<std::pair<int, int>> good;

    const auto add_good = [&](const int src, const int dst) {
        if (good.find(std::make_pair(dst, src)) != good.end()) {
            Answer(src, dst);
        }
        good.emplace(src, dst);
    };

    for (int src = 1; src <= 2 * N; ++src) {
        if (graph[src].size() == 1) {
            add_good(src, graph[src].front());
        }
        else {
            for (int ng = 0; ng < 3; ++ng) {
                const auto check = graph[src][ng];
                Vec<int> ask;
                for (const auto dst: graph[src]) {
                    if (check != dst) {
                        ask.push_back(dst);
                    }
                }
                if (difference(src, ask) == 1) {
                    add_good(src, check);
                }
            }
        }
    }
}

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