oj.uz

답안 #221643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
221643 2020-04-10T17:28:51 Z rama_pang CEOI16_icc (CEOI16_icc) C++14
100 / 100
 151 ms 636 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<vector<int>> components;

int Query(vector<int> A, vector<int> B) {
  if (A.empty() || B.empty()) return 0;
  return query(A.size(), B.size(), A.data(), B.data());
}

int QueryComponent(vector<int> A, vector<int> B) {
  vector<int> P, Q;
  for (auto i : A) {
    for (auto j : components[i]) {
      P.emplace_back(j);
    }
  }
  for (auto i : B) {
    for (auto j : components[i]) {
      Q.emplace_back(j);
    }
  }
  return Query(P, Q);
}

void Answer(int A, int B) {
  return setRoad(A, B);
}

pair<int, int> BinarySearch(vector<int> A, vector<int> B, bool onComponent) {
  if (A.size() < B.size()) swap(A, B);
  if (A.size() == 1 && B.size() == 1) return {A[0], B[0]};

  int mid = A.size() / 2;
  vector<int> L(begin(A), begin(A) + mid), R(begin(A) + mid, end(A));

  bool res;
  if (onComponent) {
    if (R.empty() || QueryComponent(L, B)) {
      return BinarySearch(L, B, onComponent);
    } else {
      return BinarySearch(R, B, onComponent);
    }
  } else {
    if (R.empty() || Query(L, B)) {
      return BinarySearch(L, B, onComponent);
    } else {
      return BinarySearch(R, B, onComponent);
    }
  }
}

void MergeComponent(int C1, int C2) {
  vector<int> Merged;
  for (auto i : components[C1]) Merged.emplace_back(i);
  for (auto i : components[C2]) Merged.emplace_back(i);
  components[C1].clear();
  components[C2].clear();
  sort(begin(components), end(components), [&](const vector<int> &a, const vector<int> &b) {
    return a.size() > b.size();
  });

  while (!components.empty() && components.back().empty()) components.pop_back();
  components.emplace_back(Merged);
}

pair<int, int> RecoverFromXor(int Xor) {
  int X = 0;
  int resA = 0, resB = 0;
  for (int i = 0; i < 7; i++) {
    if (Xor & (1 << i)) {
      X = i;
      resB |= 1 << i;
      break;
    }
  }

  for (int i = 0; i < 7; i++) {
    if (i == X) continue;
    if (Xor & (1 << i)) { // i-th bit in Xor is ON, so we query check if A = 0 and B = 1 or otherwise
      vector<int> A, B;
      for (int k = 0; k < components.size(); k++) {
        if ((k & (1 << i)) && (k & (1 << X))) { // i-th and X-th bit is ON
          B.emplace_back(k);
        } else if (!(k & (1 << i)) && !(k & (1 << X))) {
          A.emplace_back(k);
        }
      }
      if (QueryComponent(A, B)) { // A = 0 and B = 1
        resB |= 1 << i;
      } else {
        resA |= 1 << i;
      }
    } else { // Check if A = B = 0 or A = B = 1
      vector<int> A, B;
      for (int k = 0; k < components.size(); k++) {
        if ((k & (1 << i)) && (k & (1 << X))) { // i-th and X-th bit is ON
          B.emplace_back(k);
        } else if ((k & (1 << i)) && !(k & (1 << X))) {
          A.emplace_back(k);
        }
      }
      if (QueryComponent(A, B)) { // A = 1 and B = 1
        resA |= 1 << i;
        resB |= 1 << i;
      }
    }
  }

  return {resA, resB};
}

void run(int N) {
  for (int i = 1; i <= N; i++) {
    components.emplace_back(vector<int>{i});
  }

  for (int i = 1; i < N; i++) {
    int Xor = 0;
    for (int j = 0; j < 7; j++) {
      vector<int> A, B;
      for (int k = 0; k < components.size(); k++) {
        if (k & (1 << j)) {
          A.emplace_back(k);
        } else {
          B.emplace_back(k);
        }
      }
      if (QueryComponent(A, B)) {
        Xor |= 1 << j;
      }
    }

    // Binary Search to find edge's endpoint
    auto TwoComp = RecoverFromXor(Xor);
    auto Edge = BinarySearch(components[TwoComp.first], components[TwoComp.second], false);
    Answer(Edge.first, Edge.second);
    MergeComponent(TwoComp.first, TwoComp.second);
  }
}

Compilation message

icc.cpp: In function 'std::pair<int, int> BinarySearch(std::vector<int>, std::vector<int>, bool)':
icc.cpp:39:8: warning: unused variable 'res' [-Wunused-variable]
   bool res;
        ^~~
icc.cpp: In function 'std::pair<int, int> RecoverFromXor(int)':
icc.cpp:84:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int k = 0; k < components.size(); k++) {
                       ~~^~~~~~~~~~~~~~~~~~~
icc.cpp:98:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int k = 0; k < components.size(); k++) {
                       ~~^~~~~~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:124:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int k = 0; k < components.size(); k++) {
                       ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 512 KB Ok! 114 queries used.
2 Correct 11 ms 512 KB Ok! 113 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 512 KB Ok! 641 queries used.
2 Correct 42 ms 512 KB Ok! 547 queries used.
3 Correct 44 ms 512 KB Ok! 565 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 568 KB Ok! 1552 queries used.
2 Correct 133 ms 512 KB Ok! 1351 queries used.
3 Correct 151 ms 512 KB Ok! 1531 queries used.
4 Correct 147 ms 512 KB Ok! 1520 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 512 KB Ok! 1500 queries used.
2 Correct 144 ms 512 KB Ok! 1499 queries used.
3 Correct 146 ms 512 KB Ok! 1463 queries used.
4 Correct 150 ms 512 KB Ok! 1550 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 512 KB Ok! 1463 queries used.
2 Correct 141 ms 512 KB Ok! 1467 queries used.
3 Correct 138 ms 636 KB Ok! 1465 queries used.
4 Correct 141 ms 512 KB Ok! 1484 queries used.
5 Correct 148 ms 512 KB Ok! 1548 queries used.
6 Correct 140 ms 512 KB Ok! 1489 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 512 KB Ok! 1470 queries used.
2 Correct 149 ms 512 KB Ok! 1463 queries used.