제출 #1307401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307401		KickingKun	카멜레온의 사랑 (JOI20_chameleon)	C++20	100 / 100	36 ms	488 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 findEdge(int x, const vector <int> &ve) {
  int pre = -1;
  while (pre + 1 < ve.size() && adj[x].size() < 3) {
    vector <int> ask = {x};
    for (int i = pre + 1; i < ve.size(); i++)
      ask.emplace_back(ve[i]);
    if (Query(ask) == ask.size()) return;

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

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

    if (nxt == -1) return;
    adj[x].emplace_back(ve[nxt]);
    adj[ve[nxt]].emplace_back(x);
    pre = nxt;
  }
}

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

  // phan 1...i-1 thanh 2 tap
  // tim j de noi canh i -> j
  for (int i = 1; i <= 2 * N; i++) {
    for (int x = 1; x < i; x++) c[x] = -1;
    for (int x = 1; x < i; x++) if (c[x] == -1) {
      dfs(x, 0);
    }

    vector <int> L, R;
    for (int x = 1; x < i; x++) {
      if (c[x] == 0) L.emplace_back(x);
      else R.emplace_back(x);
    }

    findEdge(i, L);
    findEdge(i, R);
  }

  for (int i = 1; i <= 2 * N; i++) c[i] = -1;
  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: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36