Submission #1277853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277853		avighna	Chameleon's Love (JOI20_chameleon)	C++20	44 / 100	48 ms	568 KiB

chameleon

#include <bits/stdc++.h>

int Query(const std::vector<int> &p);
void Answer(int a, int b);

void Solve(int N) {
  std::vector<std::vector<int>> adj(2 * N + 1), ans(2 * N + 1);

  auto add = [&](int u, int v) {
    adj[u].push_back(v);
    ans[u].push_back(v);
    adj[v].push_back(u);
    ans[v].push_back(u);
  };

  auto bipartite = [&](int n) -> std::array<std::vector<int>, 2> {
    std::vector<int> a, b;
    if (n == 0) {
      return {a, b};
    }
    std::vector<bool> color(n + 1), vis(n + 1);
    auto dfs = [&](auto &&self, int u) {
      if (vis[u]) {
        return;
      }
      vis[u] = true;
      for (int &i : adj[u]) {
        color[i] = !color[u];
        self(self, i);
      }
    };
    for (int i = 1; i <= n; ++i) {
      dfs(dfs, i);
    }
    for (int i = 1; i <= n; ++i) {
      (color[i] ? a : b).push_back(i);
    }
    return {a, b};
  };

  for (int i = 1; i <= 2 * N; ++i) {
    for (auto &a : bipartite(i - 1)) {
      int j = 0;
      while (j != a.size()) {
        j = *std::ranges::partition_point(std::views::iota(0, int(a.size())), [&](int len) {
          std::vector<int> pref(len + 1);
          for (int _ = 0; _ <= len; ++_) {
            pref[_] = a[_];
          }
          for (int &x : adj[i]) {
            auto it = std::find(pref.begin(), pref.end(), x);
            if (it != pref.end()) {
              pref.erase(it);
            }
          }
          pref.push_back(i);
          return Query(pref) > pref.size() - 1;
        });
        if (j != a.size()) {
          add(i, a[j]);
        }
      }
    }
  }

  auto remove = [&](int u, int v) {
    auto it1 = std::find(ans[u].begin(), ans[u].end(), v);
    auto it2 = std::find(ans[v].begin(), ans[v].end(), u);
    if (it1 != ans[u].end()) {
      ans[u].erase(it1);
    }
    if (it2 != ans[v].end()) {
      ans[v].erase(it2);
    }
  };

  for (int u = 1; u <= 2 * N; ++u) {
    if (adj[u].size() == 1) {
      continue;
    }
    int a = adj[u][0], b = adj[u][1], c = adj[u][2];
    if (Query({u, a, b}) == 1) {
      remove(u, c);
    } else if (Query({u, a, c}) == 1) {
      remove(u, b);
    } else {
      remove(u, a);
    }
  }

  for (int i = 1; i <= 2 * N; ++i) {
    if (i < ans[i][0]) {
      Answer(i, ans[i][0]);
    }
  }
}

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