Submission #1289217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289217		aeg	카멜레온의 사랑 (JOI20_chameleon)	C++20	60 / 100	26 ms	600 KiB

chameleon

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

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

  if (N <= 50) {
    for (int i = 0; i < (N << 1); i++) {
      for (int j = i + 1; j < (N << 1); j++) {
        vector<int> toquer = {i + 1, j + 1};
        int ret = Query(toquer);
        if (ret == 1) {
          adj[i].insert(j);
          adj[j].insert(i);
        }
      }
    }
  }

  else {
    for (int i = N; i < (N << 1); i++) {
      int l = 0, r = N - 1;
      int ll = 0;
      int ans = INT_MAX;

      while (adj[i].size() < 3) {
        while (l <= r) {
          int m = (l + r) >> 1;
          vector<int> toans = {i + 1};
          for (int j = ll; j <= m; j++)
            toans.push_back(j + 1);

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

  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: 0 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36