Submission #213592

#	Time	Username	Problem	Language	Result	Execution time	Memory
213592		eriksuenderhauf	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	89 ms	512 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define vi vector<int>
#define trav(x, a) for (const auto& x: a)
#define pb push_back
using namespace std;
const int N = 1005;
vector<int> adj[N], lv[N];

void Solve(int n) {
  for (int i = 1; i <= 2*n; i++) {
    vi c[2], vis(i+1, 0);
    function<void(int,int)> dfs = [&](int u, int f){
      c[f/2].pb(u); vis[u] = 1;
      trav(v, adj[u])
        if (!vis[v])
          dfs(v, f^2);
    };
    for (int j = 1; j < i; j++)
      if (!vis[j])
        dfs(j, 1);
    for (int j = 0; j < 2; j++) {
      vi ask = c[j];
      while (1) {
        ask.pb(i);
        if (Query(ask) == sz(ask))
          break;
        ask.pop_back();
        int lo = 0, hi = sz(ask)-1;
        while (lo <= hi) {
          int mi = (lo+hi) / 2;
          vi tmp;
          for (int k = 0; k <= mi; k++)
            tmp.pb(ask[k]);
          tmp.pb(i);
          if (Query(tmp) != sz(tmp))
            hi = mi - 1;
          else
            lo = mi + 1;
        }
        adj[i].pb(ask[lo]);
        adj[ask[lo]].pb(i);
        vi tmp;
        for (int i = lo+1; i < sz(ask); i++)
          tmp.pb(ask[i]);
        swap(tmp, ask);
      }
    }
  }
  for (int i = 1; i <= 2*n; i++) {
    if (sz(adj[i]) == 1) {
      if (adj[i][0] < i)
        Answer(adj[i][0], i);
      continue;
    }
    trav(x, adj[i]) {
      vector<int> tmp = {i};
      trav(y, adj[i]) {
        if (x != y)
          tmp.pb(y);
      }
      if (Query(tmp) == 1) {
        lv[i].pb(x); // ->
        lv[x].pb(i); // <-
        break;
      }
    }
  }
  for (int i = 1; i <= 2*n; i++) {
    if (sz(adj[i]) == 1)
      continue;
    set<int> tmp(lv[i].begin(), lv[i].end());
    trav(x, adj[i]) {
      if (tmp.count(x))
        continue;
      if (i > x) // !
        Answer(i, x);
    }
  }
}

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