Submission #937781

#	Time	Username	Problem	Language	Result	Execution time	Memory
937781		Pring	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	40 ms	856 KiB

chameleon

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

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 1005;
vector<int> edge[MXN];
set<pii> S;

void BSH(vector<int> v, int x) {
    // printf("BSH\n");
    auto check = [&]() -> bool {
        v.push_back(x);
        bool f = (Query(v) != v.size());
        v.pop_back();
        return f;
    };
    do {
        int l = 0, r = v.size();
        // printf("%d %d\n", l, r);
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            // printf("%d %d\n", l, r);
            vector<int> w(mid);
            copy(v.begin(), v.begin() + mid, w.begin());
            w.push_back(x);
            (Query(w) != w.size() ? r : l) = mid;
        }
        edge[x].push_back(v[l]);
        edge[v[l]].push_back(x);
        // printf("ADD %d %d\n", x, v[l]);
        S.insert(mp(min(x, v[l]), max(x, v[l])));
        v.erase(v.begin() + l);
    } while (check());
    // printf("FFF");
}

void DO(vector<int> &v) {
    if (v.empty()) return;
    // for (auto &i : v) printf("%d ", i);
    // printf("\n");
    vector<int> a, b;
    for (auto &i : v) {
        a.push_back(i);
        if (Query(a) < a.size()) {
            a.pop_back();
            b.push_back(i);
        }
    }
    // for (auto &i : a) printf("%d ", i);
    // printf("\n");
    for (auto &i : b) BSH(a, i);
    DO(b);
}

void KILL(int id) {
    auto f = [&](int id, int a, int b) -> int {
        vector<int> v{id, a, b};
        return Query(v);
    };
    auto g = [&](int id, int a, int b, int c) -> int {
        if (f(id, a, b) == 1) return c;
        if (f(id, b, c) == 1) return a;
        return b;
    };
    if (edge[id].size() == 1) return;
    int a = edge[id][0], b = edge[id][1], c = edge[id][2];
    int d = g(id, a, b, c);
    if (id > d) swap(id, d);
    S.erase(mp(id, d));
}

void Solve(int n) {
    // printf("PRING\n");
    int N = n * 2;
    vector<int> v;
    FOR(i, 1, N + 1) v.push_back(i);

    vector<int> w(1, 1);
    // printf("%d\n", Query(w));

    DO(v);
    FOR(i, 1, N + 1) KILL(i);
    // if (S.size() != n) printf("WA\n");
    // else printf("AC\n");
    for (auto i : S) Answer(i.fs, i.sc);
}

Compilation message (stderr)

chameleon.cpp: In lambda function:
chameleon.cpp:20:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         bool f = (Query(v) != v.size());
      |                   ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'void BSH(std::vector<int>, int)':
chameleon.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             (Query(w) != w.size() ? r : l) = mid;
      |              ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'void DO(std::vector<int>&)':
chameleon.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if (Query(a) < a.size()) {
      |             ~~~~~~~~~^~~~~~~~~~

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