제출 #1307375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307375		KickingKun	카멜레온의 사랑 (JOI20_chameleon)	C++20	20 / 100	25 ms	480 KiB

chameleon

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

using namespace std;

namespace {

int variable_example = 1;

}  // namespace

vector <int> adj[1001];
int c[1001];

void dfs(int u, int color) {
  c[u] = color;
  for (int v: adj[u]) if (c[v] == -1) {
    dfs(v, 1 - color);
  }
}

bool haveEdge(int x, int y) {
  return find(adj[x].begin(), adj[x].end(), y) != adj[x].end();
}

void Solve(int N) {
  for (int i = 1; i <= 2 * N; i++) {
    adj[i].clear(); c[i] = -1;
  }

  for (int i = 1; i <= N; i++) {
    int pre = N;
    while (pre < 2 * N && adj[i].size() < 3) {
      int low = pre + 1, high = 2 * N, nxt = -1;
      while (low <= high) {
        int mid = (low + high) >> 1;
        vector <int> ask = {i};
        for (int x = pre + 1; x <= mid; x++)
          ask.emplace_back(x);

        if (Query(ask) < ask.size()) 
          high = (nxt = mid) - 1;
        else low = mid + 1;
      }

      if (nxt == -1) break;
      adj[i].emplace_back(nxt);
      adj[nxt].emplace_back(i);
      pre = nxt;
    }
  }

  for (int i = 1; i <= 2 * N; i++) 
    if (c[i] == -1) dfs(i, 0);

  for (int i = 1; i <= 2 * N; i++) {
    if (adj[i].size() == 3) {
      int x = adj[i][0], y = adj[i][1], z = adj[i][2];
      int crush;

      if (Query({i, x, y}) == 1) {
        crush = z;
      }
      else if (Query({i, x, z}) == 1) {
        crush = y;
      }
      else {
        crush = x;
      }

      adj[i].erase(find(adj[i].begin(), adj[i].end(), crush));
      // cerr << i << " like " << crush << endl;
    }
  }

  for (int i = 1; i <= 2 * N; i++) if (c[i] == 0) {
    if (adj[i].size() == 1) Answer(i, adj[i][0]);
    else {
      int x = adj[i][0], y = adj[i][1];
      if (haveEdge(x, i)) Answer(i, x);
      else Answer(i, y);
    }
  }
}

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