제출 #918937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918937		vjudge1	카멜레온의 사랑 (JOI20_chameleon)	C++17	44 / 100	32 ms	772 KiB

chameleon

#include "chameleon.h"

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

template <class Fun>
class y_combinator_result {
        Fun fun_;

       public:
        template <class T>
        explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

        template <class... Args>
        decltype(auto) operator()(Args &&...args) {
                return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

/* Example
        auto fun = y_combinator([&](auto self, int x) -> void {
                self(x + 1);
        });
*/

}  // 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<vector<int>> one_match(N * 2);

        for (int i = 0; i < N * 2; i++) {
                vector<int> vis(i, -1);
                auto dfs = y_combinator([&](auto dfs, int u, int _) -> void {
                        vis[u] = _;
                        for (int v : one_match[u]) {
                                if (vis[v] == -1) dfs(v, _ ^ 1);
                        }
                });
                for (int j = 0; j < i; j++) {
                        if (vis[j] == -1) dfs(j, 0);
                }
                for (int z = 0; z < 2; z++) {
                        vector<int> a;
                        for (int j = 0; j < i; j++) {
                                if (vis[j] == z) 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--;
                                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(N * 2, 0);
        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);
                }
        }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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