Submission #966308

#	Time	Username	Problem	Language	Result	Execution time	Memory
966308		kilkuwu	ICC (CEOI16_icc)	C++17	100 / 100	90 ms	800 KiB

icc

#include "icc.h"

#include <bits/stdc++.h>

constexpr int mxN = 105;
int aa[mxN], bb[mxN];
int in_comp[mxN];
std::vector<int> comps[mxN];
int comps_size;

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

int my_query(std::vector<int> a, std::vector<int> b) {
  for (int i = 0; i < (int) a.size(); i++) aa[i] = a[i] + 1;
  for (int i = 0; i < (int) b.size(); i++) bb[i] = b[i] + 1;
  return query(a.size(), b.size(), aa, bb);
}

void merge_comp(int i, int j) {
  if (comps[i].size() < comps[j].size()) {
    std::swap(i, j);
  }
  comps[i].insert(comps[i].end(), comps[j].begin(), comps[j].end());
  for (int u : comps[j]) {
    in_comp[u] = i;
  }
  comps_size--;
  std::swap(comps[j], comps[comps_size]);
  comps[comps_size].clear();
  for (int u : comps[j]) {
    in_comp[u] = j;
  }
}

std::array<std::vector<int>, 2> split_pool(int b) {
  std::vector<int> n1, n2;
  for (int i = 0; i < comps_size; i++) {
    if (i >> b & 1) {
      n1.insert(n1.end(), comps[i].begin(), comps[i].end());
    } else {
      n2.insert(n2.end(), comps[i].begin(), comps[i].end());
    }
  }
  return {n1, n2};
}

bool check_bit(int b) {
  auto [n1, n2] = split_pool(b);
  return my_query(n1, n2);
}

void deduce_one(std::vector<int>& left, std::vector<int>& right) {
  int lb = 0, rb = left.size() - 1;
  while (lb < rb) {
    int m = (lb + rb) / 2;
    // check from l -> m
    std::vector<int> to_ask;
    for (int i = lb; i <= m; i++) {
      to_ask.emplace_back(left[i]);
    }
    bool ok = my_query(to_ask, right);
    if (ok) {
      rb = m;
    } else {
      lb = m + 1;
    }
  }
  left = {left[rb]};
}

void run(int N) {
  comps_size = N;
  for (int i = 0; i < N; i++) {
    comps[i].emplace_back(i);
    in_comp[i] = i;
  }
  for (int tt = 0; tt + 1 < N; tt++) {
    int lg = std::__lg(comps_size - 1) + 1;
    for (int b = 0; b < lg; b++) {
      if (!check_bit(b)) continue;
      auto [l, r] = split_pool(b);

      deduce_one(l, r);
      deduce_one(r, l);

      setRoad(l[0] + 1, r[0] + 1);
      merge_comp(in_comp[l[0]], in_comp[r[0]]);
      break;
    }
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10