Submission #962768

#	Time	Username	Problem	Language	Result	Execution time	Memory
962768		Soumya1	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	49 ms	836 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1005;
vector<int> ad[mxN];
vector<int> all[2];
int col[mxN];
int query(vector<int> v, int l, int r, int x) {
  vector<int> a;
  for (int i = l; i <= r; i++) a.push_back(v[i]);
  a.push_back(x);
  return Query(a);
}
void dfs(int u) {
  all[col[u]].push_back(u);
  for (int v : ad[u]) {
    if (col[v] == -1) {
      col[v] = col[u] ^ 1;
      dfs(v);
    }
  }
}
void search(vector<int> v, int x) {
  if (v.empty()) return;
  int L = 0, R = v.size() - 1;
  while (L <= R) {
    if (query(v, L, R, x) == R - L + 2) break;
    int lo = L, hi = R;
    while (lo < hi) {
      int mid = (lo + hi) >> 1;
      if (query(v, L, mid, x) < mid - L + 2) hi = mid;
      else lo = mid + 1;
    }
    ad[x].push_back(v[hi]);
    ad[v[hi]].push_back(x);
    L = hi + 1;
  }
}
void Solve(int N) {
  for (int i = 1; i <= 2 * N; i++) {
    search(all[0], i);
    search(all[1], i);
    all[0].clear();
    all[1].clear();
    for (int j = 1; j <= i; j++) col[j] = -1;
    for (int j = 1; j <= i; j++) {
      if (col[j] == -1) col[j] = 0, dfs(j);
    }
  }
  vector<int> ans(2 * N + 1), out(2 * N + 1);
  for (int i = 1; i <= 2 * N; i++) {
    if (ad[i].size() == 1) {
      ans[i] = ad[i][0];
      continue;
    }
    int ii = -1, jj = -1;
    for (int j : ad[i]) {
      for (int k : ad[i]) {
        if (j == k || ii != -1) continue;
        if (Query({i, j, k}) == 1) {
          ii = j, jj = k;
        }
      }
    }
    for (int j : ad[i]) {
      if (j != ii && j != jj) out[i] = j;
    }
  }
  for (int i = 1; i <= 2 * N; i++) {
    if (ad[i].size() == 1) continue;
    for (int j : ad[i]) {
      if (j != out[i] && out[j] != i) ans[i] = j;
    }
  }
  for (int i = 1; i <= 2 * N; i++) {
    if (i < ans[i]) Answer(i, ans[i]);
  }
}

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