Submission #918923

#	Time	Username	Problem	Language	Result	Execution time	Memory
918923		vjudge1	Chameleon's Love (JOI20_chameleon)	C++17	20 / 100	28 ms	792 KiB

chameleon

#include "chameleon.h"

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

        vector<int> p(N), q(N);
        iota(p.begin(), p.end(), 0);
        iota(q.begin(), q.end(), N);
        vector<vector<int>> one_match(N * 2);

        shuffle(p.begin(), p.end(), rng);
        vector<int> cnt(2 * N);
        for (int i : p) {
                vector<int> a;
                for (int j = N; j < N * 2; j++) {
                        if (cnt[j] < 3) a.emplace_back(j);
                }
                while (true) {
                        vector<int> rem(a.size());
                        iota(rem.begin(), rem.end(), 1);
                        for (int j = 1; j <= a.size(); j <<= 1) {
                                vector<int> what(1, i);
                                for (int k : rem) {
                                        if (k & j) what.emplace_back(a[k - 1]);
                                }
                                int ok = (ask(what) != what.size());
                                vector<int> tmp;
                                for (int k : rem) {
                                        if (((k & j) > 0) == ok) tmp.emplace_back(k);
                                }
                                swap(rem, tmp);
                        }
                        if (rem.size() == 0) break;
                        assert(rem.size() == 1);
                        int x = rem[0];
                        x--;
                        cnt[a[x]]++;
                        one_match[i].emplace_back(a[x]);
                        one_match[a[x]].emplace_back(i);
                        a.erase(a.begin() + x);
                }
        }

        vector<int> answer(2 * N);
        vector<int> love(2 * N);
        vector<int> evol(2 * N);
        vector<int> done(2 * N);
        for (int i = 0; i < 2 * N; i++) {
                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 {
                        int last = -1;
                        while (done[i] == 0) {
                                done[i] = 1;
                                int a = one_match[i][0];
                                int b = one_match[i][1];
                                int c = one_match[i][2];
                                if (last == -1) {
                                        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;
                                        }
                                } else {
                                        if (last != a && ask({i, last, a}) == 1) {
                                                int nxt = last ^ b ^ c;
                                                love[i] = nxt;
                                                evol[nxt] = i;
                                                last = i;
                                                i = nxt;
                                        } else if (last != b && ask({i, last, b}) == 1) {
                                                int nxt = last ^ a ^ c;
                                                love[i] = nxt;
                                                evol[nxt] = i;
                                                last = i;
                                                i = nxt;
                                        } else {
                                                int nxt = last ^ a ^ b;
                                                love[i] = nxt;
                                                evol[nxt] = i;
                                                last = i;
                                                i = nxt;
                                        }
                                }
                        }
                }
        }
        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);
                }
        }
}

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:28:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |                         for (int j = 1; j <= a.size(); j <<= 1) {
      |                                         ~~^~~~~~~~~~~
chameleon.cpp:33:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                                 int ok = (ask(what) != what.size());
      |                                           ~~~~~~~~~~^~~~~~~~~~~~~~

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