Submission #933802

#	Time	Username	Problem	Language	Result	Execution time	Memory
933802		nguyentunglam	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	62 ms	4440 KiB

chameleon

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

using namespace std;

namespace {
const int NN = 1e3 + 10;

bool vis[NN];

vector<int> adj[NN], arr[2];

int love[NN][NN];

void dfs(int u, int g) {
  vis[u] = 1;
  arr[g].push_back(u);
  for(int &v : adj[u]) if (!vis[v]) dfs(v, g ^ 1);
}

void add (int a, int b) {
  adj[a].push_back(b);
  adj[b].push_back(a);
}

void Find (vector<int> x, int i) {
  if (x.empty()) return;
  vector<int> tmp = x;
  tmp.push_back(i);
  if (Query(tmp) == tmp.size()) return;
  if (x.size() == 1) {
    add(x[0], i);
    return;
  }
  int l = 0, r = x.size() - 1, last = -1;
  while (l <= r) {
    int mid = l + r >> 1;
    tmp = {i};
    for(int j = 0; j <= mid; j++) tmp.push_back(x[j]);
    if (Query(tmp) != tmp.size()) {
      last = mid;
      r = mid - 1;
    } else l = mid + 1;
  }
  assert(last >= 0);
  add(x[last], i);
  x.erase(x.begin() + last);
  Find(x, i);
}

void solve(int n) {
//  for(int i = 1; i <= 2 * n; i++) for(int j = i + 1; j <= 2 * n; j++) {
//    if (Query({i, j}) == 1) {
//      adj[i].push_back(j);
//      adj[j].push_back(i);
//    }
//  }

  for(int i = 2; i <= 2 * n; i++) {
    for(int j = 1; j < i; j++) vis[j] = 0;
    for(int j = 1; j < i; j++) if (!vis[j]) {
      if (arr[0].size() < arr[1].size()) dfs(j, 0);
      else dfs(j, 1);
    }
    for(int j = 0; j < 2; j++) if (!arr[j].empty()) {
      Find(arr[j], i);
      arr[j].clear();
    }
  }

  for(int i = 1; i <= 2 * n; i++) {
    assert(adj[i].size() == 1 || adj[i].size() == 3);
    if (adj[i].size() == 1) continue;
    for(int &j : adj[i]) {
      vector<int> tmp;
      tmp.push_back(i);
      for(int &k : adj[i]) if (k != j) tmp.push_back(k);
      if (Query(tmp) == 1) {
        love[i][j] = 1;
      }
    }
  }

  for(int i = 1; i <= 2 * n; i++) {
    for(int &j : adj[i]) if (i < j && love[i][j] + love[j][i] == 0) {
      Answer(i, j);
    }
  }
}
}  // namespace


void Solve(int n) {
  ::solve(n);
}

Compilation message (stderr)

chameleon.cpp: In function 'void {anonymous}::Find(std::vector<int>, int)':
chameleon.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   if (Query(tmp) == tmp.size()) return;
      |       ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~
chameleon.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if (Query(tmp) != tmp.size()) {
      |         ~~~~~~~~~~~^~~~~~~~~~~~~

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