Submission #212050

#	Time	Username	Problem	Language	Result	Execution time	Memory
212050		extraterrestrial	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	91 ms	652 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll

mt19937 rnd(239);

void dfs(int v, int cl, vector<vector<int>> &g, vector<int> &color, vector<bool> &used) {
  used[v] = true;
  color[v] = cl;
  for (auto u : g[v]) {
    if (!used[u]) {
      dfs(u, cl ^ 1, g, color, used);
    }
  }
}

void Solve(int n) {
  vector<vector<int>> g(2 * n + 1);
  vector<int> color(2 * n + 1);
  vector<bool> used(2 * n + 1);
  vector<pair<int, int>> interesting;
  for (int i = 2; i <= 2 * n; i++) {
    fill(all(used), false);
    for (int j = 1; j < i; j++) {
      if (!used[j]) {
        dfs(j, 0, g, color, used);
      }
    }
    vector<int> have0, have1;
    for (int j = 1; j < i; j++) {
      if (color[j] == 0) {
        have0.pb(j);
      }
      else {
        have1.pb(j);
      }
    }
    int cur = 0;
    while (cur < SZ(have0)) {
      vector<int> kek;
      for (int j = cur; j < SZ(have0); j++) {
        kek.pb(have0[j]);
      }
      kek.pb(i);
      if (Query(kek) >= SZ(kek)) {
        break;
      }
      int l = cur - 1, r = SZ(have0);
      while (r - l > 1) {
        int mid = (l + r) / 2;
        vector<int> kek;
        for (int j = cur; j <= mid; j++) {
          kek.pb(have0[j]);
        }
        kek.pb(i);
        if (Query(kek) < SZ(kek)) {
          r = mid;
        }
        else {
          l = mid;
        }
      }
      if (r < SZ(have0)) {
        int v = have0[r];
        interesting.pb({v, i});
        g[v].pb(i);
        g[i].pb(v);
        cur = r + 1;
      }
      else {
        break;
      }
    }
    cur = 0;
    while (cur < SZ(have1)) {
      vector<int> kek;
      for (int j = cur; j < SZ(have1); j++) {
        kek.pb(have1[j]);
      }
      kek.pb(i);
      if (Query(kek) >= SZ(kek)) {
        break;
      }
      int l = cur - 1, r = SZ(have1);
      while (r - l > 1) {
        int mid = (l + r) / 2;
        vector<int> kek;
        for (int j = cur; j <= mid; j++) {
          kek.pb(have1[j]);
        }
        kek.pb(i);
        if (Query(kek) < SZ(kek)) {
          r = mid;
        }
        else {
          l = mid;
        }
      }
      if (r < SZ(have1)) {
        int v = have1[r];
        interesting.pb({v, i});
        g[v].pb(i);
        g[i].pb(v);
        cur = r + 1;
      }
      else {
        break;
      } 
    }
  }
  vector<pair<int, int>> rez;
  for (auto it : interesting) {
    vector<int> kek;
    for (int i = 1; i <= 2 * n; i++) {
      if (i != it.F && i != it.S) {
        kek.pb(i);
      }
    }
    if (Query(kek) < n) {
      rez.pb(it);
    }
  }
  for (auto it : rez) {
    Answer(it.F, it.S);
  }
}

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