oj.uz

Submission #966308

# Submission time Handle Problem Language Result Execution time Memory
966308 2024-04-19T16:41:17 Z kilkuwu ICC (CEOI16_icc) C++17
100 / 100
 90 ms 800 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Ok! 93 queries used.
2 Correct 4 ms 600 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 604 KB Ok! 521 queries used.
2 Correct 33 ms 648 KB Ok! 650 queries used.
3 Correct 26 ms 604 KB Ok! 641 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 600 KB Ok! 1349 queries used.
2 Correct 90 ms 800 KB Ok! 1599 queries used.
3 Correct 76 ms 604 KB Ok! 1583 queries used.
4 Correct 74 ms 636 KB Ok! 1489 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 604 KB Ok! 1437 queries used.
2 Correct 71 ms 640 KB Ok! 1381 queries used.
3 Correct 90 ms 604 KB Ok! 1546 queries used.
4 Correct 71 ms 628 KB Ok! 1392 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 620 KB Ok! 1584 queries used.
2 Correct 78 ms 600 KB Ok! 1541 queries used.
3 Correct 77 ms 640 KB Ok! 1572 queries used.
4 Correct 78 ms 604 KB Ok! 1583 queries used.
5 Correct 72 ms 636 KB Ok! 1457 queries used.
6 Correct 75 ms 612 KB Ok! 1529 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 604 KB Ok! 1583 queries used.
2 Correct 87 ms 648 KB Ok! 1594 queries used.