Submission #918889

#	Time	Username	Problem	Language	Result	Execution time	Memory
918889		vjudge1	Chameleon's Love (JOI20_chameleon)	C++17	40 / 100	15 ms	600 KiB

chameleon

#include "chameleon.h"

#include <bits/stdc++.h>
using namespace std;

void Solve(int N) {
        auto ask = [&](vector<int> p) {
                for (auto& x : p) x++;
                return Query(p);
        };

        vector<vector<int>> one_match(N * 2);
        for (int i = 0; i < 2 * N; i++) {
                for (int j = i + 1; j < 2 * N; j++) {
                        if (ask({i, j}) == 1) one_match[i].emplace_back(j), one_match[j].emplace_back(i);
                }
        }
        vector<int> answer(2 * N);
        vector<int> love(2 * N);
        vector<int> evol(2 * N);
        for (int i = 0; i < 2 * N; i++) {
                assert(one_match[i].size() % 2);
                if (one_match[i].size() == 1) {
                        if (answer[i]) continue;
                        answer[i] = 1;
                        answer[one_match[i][0]] = 1;
                        Answer(i + 1, one_match[i][0] + 1);
                } else {
                        assert(one_match[i].size() == 3);
                        int a = one_match[i][0];
                        int b = one_match[i][1];
                        int c = one_match[i][2];
                        if (ask({i, a, b}) == 1) {
                                love[i] = c;
                                evol[c] = i;
                        } else if (ask({i, a, c}) == 1) {
                                love[i] = b;
                                evol[b] = i;
                        } else {
                                love[i] = a;
                                evol[a] = i;
                        }
                }
        }
        for (int i = 0; i < 2 * N; i++) {
                if (answer[i]) continue;
                for (int j : one_match[i]) {
                        if (j == love[i]) continue;
                        if (j == evol[i]) continue;
                        answer[i] = answer[j] = 1;
                        Answer(i + 1, j + 1);
                }
        }
}

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