oj.uz

답안 #570317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
570317 2022-05-29T08:12:46 Z 600Mihnea CEOI16_icc (CEOI16_icc) C++17
61 / 100
 182 ms 588 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

mt19937 rng((long long) (new char));

int get(vector<int> a, vector<int> b) {
  if (a.empty() || b.empty()) {
    return 0;
  }
  return query((int) a.size(), (int) b.size(), a.data(), b.data());
}

vector<int> operator + (vector<int> a, vector<int> b) {
  for (auto &x : b) {
    a.push_back(x);
  }
  return a;
}

const int N = 100 + 7;
int t[N];

int get_root(int a) {
  if (t[a] == a) {
    return a;
  } else {
    return t[a] = get_root(t[a]);
  }
}

void join(int a, int b) {
  t[get_root(a)] = get_root(b);
}

void run(int n) {
  for (int i = 1; i <= n; i++) {
    t[i] = i;
  }
  for (int step = 1; step <= n - 1; step++) {
    vector<vector<int>> comps;
    for (int i = 1; i <= n; i++) {
      if (get_root(i) == i) {
        vector<int> currentComp;
        for (int j = 1; j <= n; j++) {
          if (get_root(j) == i) {
            currentComp.push_back(j);
          }
        }
        comps.push_back(currentComp);
      }
    }

    assert((int) comps.size() == n - step + 1);
    assert((int) comps.size() >= 2);

    vector<int> p1, p2;
    while (1) {
      p1.clear();
      p2.clear();
      shuffle(comps.begin(), comps.end(), rng);
      for (auto &comp : comps) {
        if ((int) p1.size() < (int) p2.size()) {
          p1 = p1 + comp;
        } else {
          p2 = p2 + comp;
        }
      }
      assert((int) p1.size() + (int) p2.size() == n);
      if (get(p1, p2) == 1) {
        break;
      }
    }
    while ((int) p1.size() > 1 || (int) p2.size() > 1) {
      shuffle(p1.begin(), p1.end(), rng);
      shuffle(p2.begin(), p2.end(), rng);
      if ((int) p2.size() < (int) p1.size()) {
        swap(p1, p2);
      }
      assert((int) p1.size() <= (int) p2.size());
      vector<int> X(p2.begin(), p2.begin() + (int)p2.size() / 2), Y(p2.begin() + (int) p2.size() / 2, p2.end());
      assert((int) X.size() + (int) Y.size() == (int) p2.size());
      if (get(p1, X)) {
        p2 = X;
      } else {
        p2 = Y;
      }
    }
    assert((int) p1.size() == 1 && (int) p2.size() == 1);
    join(p1[0], p2[0]);
    setRoad(p1[0], p2[0]);
  }
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 508 KB Ok! 102 queries used.
2 Correct 5 ms 468 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 508 KB Ok! 550 queries used.
2 Correct 49 ms 468 KB Ok! 854 queries used.
3 Correct 58 ms 468 KB Ok! 818 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 504 KB Ok! 1488 queries used.
2 Correct 182 ms 512 KB Ok! 2136 queries used.
3 Correct 114 ms 468 KB Ok! 1443 queries used.
4 Correct 142 ms 508 KB Ok! 1770 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 520 KB Ok! 1516 queries used.
2 Correct 149 ms 516 KB Ok! 1587 queries used.
3 Correct 158 ms 508 KB Ok! 1948 queries used.
4 Correct 111 ms 588 KB Ok! 1430 queries used.

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 172 ms 508 KB Too many queries! 2038 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 504 KB Too many queries! 2016 out of 1625
2 Halted 0 ms 0 KB -