Submission #217163

#	Time	Username	Problem	Language	Result	Execution time	Memory
217163		rama_pang	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	67 ms	504 KiB

chameleon

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

vector<pair<int, int>> edges; // edges(a, b) if Query({a, b}) = 1

void FindEdges(vector<int> candidates, int n) { // find edges from one of vertices in candidates to i
  int lo = 0, hi = (int) candidates.size() - 1;

  while (lo < hi) {
    int mid = (lo + hi) / 2;
    vector<int> q(begin(candidates), begin(candidates) + mid + 1);
    q.emplace_back(n);
    if (Query(q) < q.size()) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }

  edges.emplace_back(candidates[hi], n); // set(candidates[1...hi] + n) has an edge while set(candidates[1...hi-1] + n) doesn't, means there is an edge between candidates[hi] and n

  vector<int> new_candidates(begin(candidates) + hi + 1, end(candidates));  
  vector<int> q(new_candidates); 
  q.emplace_back(n);

  if (Query(q) < q.size()) { // there is an edge between new_candidates and n
    return FindEdges(new_candidates, n);
  }
}

void Solve(int N) {
  vector<vector<int>> ind(4); // independent sets

  for (int i = 1; i <= 2 * N; i++) {
    vector<bool> is_independent(4, false); // is ind[j] independent after adding i?
    
    for (int j = 0; j < 4; j++) {
      vector<int> q(ind[j]);
      q.emplace_back(i);
      if (Query(q) < q.size()) { // there is an edge between ind[j] and i
        FindEdges(ind[j], i);
      } else { 
        is_independent[j] = true; // adding i to ind[j] still maintain its independency
      }
    }

    for (int j = 0; j < 4; j++) {
      if (is_independent[j]) { // adding i to ind[j] still maintain its independency, so we can put i in ind[j]
        ind[j].emplace_back(i);
        break;
      }
    }
  }

  vector<vector<int>> adj(2 * N + 1);
  vector<bool> determined(2 * N + 1, false); // determined[i] means i has already been answered

  for (auto &e : edges) {
    int a = e.first, b = e.second;
    adj[a].emplace_back(b);
    adj[b].emplace_back(a);
  }

  auto IsSpecial = [&](int a, int b) { // determine if a and b has the same color
    vector<int> all_except_a_and_b;
    for (int i = 1; i <= 2 * N; i++) {
      if (i == a || i == b) continue;
      all_except_a_and_b.emplace_back(i);
    }
    return Query(all_except_a_and_b) < N; // If query returns N, then a and b is not the same color
  };

  for (int i = 1; i <= 2 * N; i++) {
    if (determined[i]) continue;
    for (auto &j : adj[i]) {
      if (determined[j]) continue;
      if (IsSpecial(i, j)) {
        determined[i] = true;
        determined[j] = true;
        Answer(i, j);
        break;
      }
    }
  }
}

Compilation message (stderr)

chameleon.cpp: In function 'void FindEdges(std::vector<int>, int)':
chameleon.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (Query(q) < q.size()) {
         ~~~~~~~~~^~~~~~~~~~
chameleon.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (Query(q) < q.size()) { // there is an edge between new_candidates and n
       ~~~~~~~~~^~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (Query(q) < q.size()) { // there is an edge between ind[j] and i
           ~~~~~~~~~^~~~~~~~~~

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