Submission #216659

#	Time	Username	Problem	Language	Result	Execution time	Memory
216659		AlexPop28	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	85 ms	888 KiB

chameleon

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

int Check(const vector<int> &v, int n, int node) {
  vector<int> u(v.begin(), v.begin() + n + 1);
  u.emplace_back(node);
  return Query(u);
}

void Solve(int n) {
  vector<vector<int>> adj(2 * n + 1);
  vector<vector<int>> sides(2);
  vector<int> col(2 * n + 1);
  
  function<void(int, int)> Split = [&](int node, int c) {
    sides[c].emplace_back(node);
    col[node] = c;
    for (int &x : adj[node]) {
      if (col[x] == -1) {
        Split(x, c ^ 1);
      }
    }
  };

  auto AddEdge = [&](int a, int b) {
    adj[a].emplace_back(b);
    adj[b].emplace_back(a);
  };

  for (int i = 1; i <= 2 * n; ++i) {
    sides[0].clear(); sides[1].clear();
    fill(col.begin(), col.end(), -1);
    for (int j = 1; j < i; ++j) {
      if (col[j] == -1) {
        Split(j, 0);
      }
    }

    for (int side = 0; side < 2; ++side) {
      auto v = sides[side];

      while (!v.empty() && Check(v, v.size() - 1, i) <= v.size()) {
        int lo = 0, hi = v.size() - 1, ans = -1;
        while (lo <= hi) {
          int mid = lo + (hi - lo) / 2;
          if (Check(v, mid, i) <= mid + 1) {
            hi = mid - 1;
            ans = mid;
          } else {
            lo = mid + 1;
          }
        }
        
        int x = v[ans];
        AddEdge(i, x);
        v = vector<int>(v.begin() + ans + 1, v.end());
      }
    }
  }

  int cnt_ans = 0;
  vector<set<int>> link(2 * n + 1);
  
  auto AddLink = [&](int x, int y) {
    link[x].emplace(y);
    if (link[y].count(x)) {
      ++cnt_ans;
      Answer(x, y);
    }
  };

  for (int i = 1; i <= 2 * n; ++i) {
    if ((int)adj[i].size() == 1) {
      AddLink(i, adj[i][0]);
      continue;
    }
    
    int x = Query({i, adj[i][0], adj[i][1]});
    int y = Query({i, adj[i][0], adj[i][2]});

    int z = 2;
    if (x == 2 && y == 2) z = 1;

    if (x == 1) {
      AddLink(i, adj[i][0]);
      AddLink(i, adj[i][1]);
    }
    if (y == 1) {
      AddLink(i, adj[i][0]);
      AddLink(i, adj[i][2]);
    }
    if (z == 1) {
      AddLink(i, adj[i][1]);
      AddLink(i, adj[i][2]);
    }
  }
}  

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:43:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (!v.empty() && Check(v, v.size() - 1, i) <= v.size()) {
                            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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