Submission #1289223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289223		aeg	Chameleon's Love (JOI20_chameleon)	C++20	100 / 100	51 ms	564 KiB

chameleon

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

void dfs(int s, vector<set<int>> const &adj, vector<int> &a, vector<int> &b,
         vector<bool> &vis, bool flag) {
  if (vis[s])
    return;
  vis[s] = true;
  if (flag)
    b.push_back(s);
  else
    a.push_back(s);
  for (auto &x : adj[s]) {
    if (vis[x])
      continue;
    dfs(x, adj, a, b, vis, (flag xor true));
  }
}

void bipartite(vector<set<int>> const &adj, vector<int> &a, vector<int> &b,
               int ind) {
  vector<bool> vis(ind, false);
  for (int i = 0; i < ind; i++) {
    if (!vis[i])
      dfs(i, adj, a, b, vis, false);
  }
}

void Solve(int N) {
  vector<set<int>> adj(N << 1);

  for (int i = 0; i < (N << 1); i++) {
    vector<int> a, b;
    bipartite(adj, a, b, i);
    int l = 0, r = a.size() - 1;
    int ll = 0;
    int ans = INT_MAX;

    while (true) {
      vector<int> totest = {i + 1};
      for (int i = ll; i < a.size(); i++)
        totest.emplace_back(a[i] + 1);
      int test = Query(totest);
      if (test == totest.size())
        break;
      while (l <= r) {
        int m = (l + r) >> 1;
        vector<int> toans = {i + 1};
        for (int j = ll; j <= m; j++)
          toans.push_back(a[j] + 1);

        int ret = Query(toans);
        if (ret != toans.size()) {
          ans = min(ans, m);
          r = m - 1;
        } else {
          l = m + 1;
        }
      }
      adj[i].insert(a[ans]);
      adj[a[ans]].insert(i);
      l = ans + 1;
      ll = ans + 1;
      r = a.size() - 1;
      ans = INT_MAX;
    }
    l = 0, r = b.size() - 1;
    ll = 0;
    ans = INT_MAX;

    while (true) {
      vector<int> totest = {i + 1};
      for (int i = ll; i < b.size(); i++)
        totest.emplace_back(b[i] + 1);
      int test = Query(totest);
      if (test == totest.size())
        break;
      while (l <= r) {
        int m = (l + r) >> 1;
        vector<int> toans = {i + 1};
        for (int j = ll; j <= m; j++)
          toans.push_back(b[j] + 1);

        int ret = Query(toans);
        if (ret != toans.size()) {
          ans = min(ans, m);
          r = m - 1;
        } else {
          l = m + 1;
        }
      }
      adj[i].insert(b[ans]);
      adj[b[ans]].insert(i);
      l = ans + 1;
      ll = ans + 1;
      r = b.size() - 1;
      ans = INT_MAX;
    }
  }

  vector<pair<int, int>> toign;

  for (int i = 0; i < (N << 1); i++) {
    if (adj[i].empty() || adj[i].size() == 1) {
      continue;
    } else {
      vector<int> tmp;
      for (auto x : adj[i])
        tmp.push_back(x);

      for (int k = 0; k < 3; k++) {
        vector<int> toask = {i + 1};
        for (int j = 0; j < 3; j++)
          if (j != k)
            toask.push_back(tmp[j] + 1);

        int ans = Query(toask);
        if (ans == 1) {
          toign.emplace_back(i, tmp[k]);
          break;
        }
      }
    }
  }

  for (auto &[x, y] : toign) {
    adj[x].erase(y);
    adj[y].erase(x);
  }

  for (int i = 0; i < (N << 1); i++) {
    if (adj[i].empty())
      continue;
    else {
      Answer(i + 1, (*adj[i].begin()) + 1);
      adj[*adj[i].begin()].clear();
      adj[i].clear();
    }
  }
}

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