Submission #212906

#	Time	Username	Problem	Language	Result	Execution time	Memory
212906		keko37	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	59 ms	512 KiB

chameleon

#include "chameleon.h"
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;

int n;
int bio[MAXN], love[MAXN];
vector <int> v[MAXN], comp[2];

//int Query (vector <int> & p) {}
//void Answer (int a, int b) {}

void dfs (int x, bool col) {
    if (bio[x] != -1) return;
    bio[x] = col;
    comp[col].push_back(x);
    for (auto sus : v[x]) {
        dfs(sus, !col);
    }
}

void split (int m) {
    comp[0].clear(); comp[1].clear();
    memset(bio, -1, sizeof bio);
    for (int i = 1; i <= m; i++) {
        if (bio[i] == -1) dfs(i, 0);
    }
}

bool ask (int curr, int lo, int hi, vector <int> & c) {
    vector <int> q(hi - lo + 1);
    for (int i = lo; i <= hi; i++) {
        q[i - lo] = c[i];
    }
    q.push_back(curr);
    return Query(q) < q.size();
}

int gen_edge (int curr, vector <int> & c, int lo) {
    int hi = (int)c.size() - 1;
    if (!ask(curr, lo, hi, c)) return c.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (ask(curr, lo, mid, c)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

void build () {
    for (int i = 1; i <= 2 * n; i++) {
        split(i - 1);
        for (int j = 0; j < 2; j++) {
            if (comp[j].empty()) continue;
            int lo = 0;
            while (lo < comp[j].size()) {
                int res = gen_edge(i, comp[j], lo);
                if (res < comp[j].size()) {
                    int sus = comp[j][res];
                    v[sus].push_back(i);
                    v[i].push_back(sus);
                }
                lo = res + 1;
            }
        }
    }
}

void Solve (int N) {
	n = N;
    build();
    for (int i = 1; i <= 2 * n; i++) {
        if (v[i].size() == 3) {
            int a = v[i][0], b = v[i][1], c = v[i][2];
            vector <int> q;
            q = {i, a, b}; if (Query(q) == 1) love[i] = c;
            q = {i, a, c}; if (Query(q) == 1) love[i] = b;
            q = {i, b, c}; if (Query(q) == 1) love[i] = a;
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        for (auto sus : v[i]) {
            if (love[i] != sus && love[sus] != i && i < sus) Answer(i, sus);
        }
    }
}

/*int main () {
    return 0;
}*/

Compilation message (stderr)

chameleon.cpp: In function 'bool ask(int, int, int, std::vector<int>&)':
chameleon.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return Query(q) < q.size();
            ~~~~~~~~~^~~~~~~~~~
chameleon.cpp: In function 'void build()':
chameleon.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (lo < comp[j].size()) {
                    ~~~^~~~~~~~~~~~~~~~
chameleon.cpp:63:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (res < comp[j].size()) {
                     ~~~~^~~~~~~~~~~~~~~~

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