제출 #918921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918921		vjudge1	Chameleon's Love (JOI20_chameleon)	C++17	0 / 100	1 ms	344 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);
                }
                int repeat = 3;
                while (repeat--) {
                        int low = 0, high = a.size() - 1;
                        while (low < high) {
                                int mid = low + high >> 1;
                                vector<int> what;
                                for (int j = low; j <= mid; j++) what.emplace_back(a[j]);
                                what.emplace_back(i);
                                if (ask(what) == what.size()) {
                                        low = mid + 1;
                                } else {
                                        high = mid;
                                }
                        }
                        cnt[a[high]]++;
                        one_match[i].emplace_back(a[high]);
                        one_match[a[high]].emplace_back(i);
                        a.erase(a.begin() + high);
                }
        }

        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);
                }
        }
}

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

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:29:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |                                 int mid = low + high >> 1;
      |                                           ~~~~^~~~~~
chameleon.cpp:33:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                                 if (ask(what) == what.size()) {
      |                                     ~~~~~~~~~~^~~~~~~~~~~~~~

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