oj.uz

Submission #1086395

# Submission time Handle Problem Language Result Execution time Memory
1086395 2024-09-10T12:42:51 Z juicy ICC (CEOI16_icc) C++17
90 / 100
 107 ms 652 KB 
#include "icc.h"

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 105;

int pr[N];
vector<int> ver[N];

int qry(vector<int> a, vector<int> b) {
  return query(a.size(), b.size(), &a[0], &b[0]);
}

int find(int u) {
  return pr[u] == u ? u : pr[u] = find(pr[u]); 
}

int find(vector<int> a, vector<int> b) {
  int l = 0, r = a.size() - 1, res = -1;
  while (l <= r) {
    int m = (l + r) / 2;
    if (qry(vector(a.begin(), a.begin() + m + 1), b)) {
      res = a[m];
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  return res;
}

void run(int n) {
  iota(pr, pr + n, 0);
  for (int i = 0; i < n; ++i) {
    ver[i].push_back(i + 1);
  }
  for (int e = 0; e < n - 1; ++e) {
    vector<int> root;
    for (int i = 0; i < n; ++i) {
      if (pr[i] == i) {
        root.push_back(i);
      }
    }
    shuffle(root.begin(), root.end(), rng);
    int m = root.size();
    vector<int> a, b, cnd;
    for (int i = 0; (1 << i) < m; ++i) {
      cnd.push_back(i);
    }
    shuffle(cnd.begin(), cnd.end(), rng);
    for (auto i : cnd) {
      vector<int>().swap(a);
      vector<int>().swap(b);
      for (int j = 0; j < m; ++j) {
        auto &v = j >> i & 1 ? a : b;
        v.insert(v.end(), ver[root[j]].begin(), ver[root[j]].end());
      }
      if (qry(a, b)) {
        break;
      }
    }
    int u = find(a, b), v = find(b, a);
    setRoad(u, v);
    --u, --v;
    for (int x : ver[pr[v]]) {
      pr[x - 1] = pr[u];
      ver[pr[u]].push_back(x);
    }
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Ok! 108 queries used.
2 Correct 5 ms 632 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 604 KB Ok! 549 queries used.
2 Correct 35 ms 636 KB Ok! 713 queries used.
3 Correct 39 ms 604 KB Ok! 711 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 640 KB Ok! 1453 queries used.
2 Correct 105 ms 600 KB Ok! 1731 queries used.
3 Correct 92 ms 640 KB Ok! 1603 queries used.
4 Correct 95 ms 644 KB Ok! 1566 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 604 KB Ok! 1557 queries used.
2 Correct 105 ms 600 KB Ok! 1540 queries used.
3 Correct 98 ms 600 KB Ok! 1676 queries used.
4 Correct 102 ms 604 KB Ok! 1509 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 600 KB Ok! 1674 queries used.
2 Correct 101 ms 600 KB Ok! 1713 queries used.
3 Correct 100 ms 636 KB Ok! 1698 queries used.
4 Correct 97 ms 640 KB Ok! 1666 queries used.
5 Correct 88 ms 632 KB Ok! 1519 queries used.
6 Correct 102 ms 652 KB Ok! 1633 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 632 KB Too many queries! 1682 out of 1625
2 Halted 0 ms 0 KB -