oj.uz

Submission #966281

# Submission time Handle Problem Language Result Execution time Memory
966281 2024-04-19T16:06:20 Z kilkuwu ICC (CEOI16_icc) C++17
0 / 100
 1 ms 604 KB 
#ifndef LOCAL
#include "icc.h"
#else 
int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);
#endif

#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;

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) a.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]);
  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], r[0]);
      break;
    }
  }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -