Submission #372434

#	Time	Username	Problem	Language	Result	Execution time	Memory
372434		KoD	Chameleon's Love (JOI20_chameleon)	C++17	40 / 100	22 ms	492 KiB

chameleon

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

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

void Solve(int N) {
    Vec<Vec<int>> graph(2 * N + 1);
    for (int u = 1; u <= 2 * N; ++u) {
        for (int v = u + 1; v <= 2 * N; ++v) {
            const auto kinds = Query({ u, v });
            if (kinds == 1) {
                graph[u].push_back(v);
                graph[v].push_back(u);
            }
        }
    }
    Vec<Vec<char>> prob(2 * N + 1, Vec<char>(2 * N + 1));
    for (int u = 1; u <= 2 * N; ++u) {
        if (graph[u].size() == 1) {
            prob[u][graph[u].front()] = true;
        }
        else {
            assert(graph[u].size() == 3);
            for (int ignore = 0; ignore < 3; ++ignore) {
                Vec<int> ask;
                ask.push_back(u);
                for (int k = 0; k < 3; ++k) {
                    if (ignore != k) {
                        ask.push_back(graph[u][k]);
                    }
                }
                if (Query(ask) == 2) {
                    prob[u][graph[u][ignore]] = true;
                }
            }
        }
    }
    for (int u = 1; u <= 2 * N; ++u) {
        for (int v = u + 1; v <= 2 * N; ++v) {
            if (prob[u][v] && prob[v][u]) {
                Answer(u, v);
            }
        }
    }
}

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