Submission #1290622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290622		lucaskojima	ICC (CEOI16_icc)	C++17	0 / 100	190 ms	327680 KiB

icc

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "icc.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N   = 100;
const int LOG = 7;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int a[N], b[N];

struct dsu {
  vector<int> e;
  ordered_set<int> rt;
  dsu(int n) : e(n + 1, -1) {
    for (int i = 1; i <= n; i++)
      rt.insert(i);
  }

  int find(int v) { return e[v] < 0 ? v : e[v] = find(v); }
  int size(int v) { return -e[find(v)]; }
  bool same(int a, int b) { return find(a) == find(b); }
  void une(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (e[a] < e[b]) swap(a, b);
    e[b] += e[a];
    e[a] = b;
    rt.erase(a);
  }
};

void run(int n) {
  dsu dsu(n);
  for (int _ = 0; _ < n - 1; _++) {
    int size_a = 0;
    int size_b = 0;

    for (int i = LOG - 1; i >= 0; i--) {
      size_a = size_b = 0;
      for (int v = 1; v <= n; v++) {
        int id = dsu.rt.order_of_key(dsu.find(v));
        if ((id >> i) & 1)
          a[size_a++] = v;
        else
          b[size_b++] = v;
      }

      if (size_a > 0 && size_b > 0 && query(size_a, size_b, a, b) == 1) break;
    }

    auto find = [](int size_x, int size_y, int *x, int *y) -> int {
      int l = 0;
      int r = size_x - 1;
      while (l != r) {
        int m = (l + r) / 2;
        if (query(m + 1, size_y, x, y) == 1)
          r = m;
        else
          l = m + 1;
      }
      return l;
    };

    int i = find(size_a, size_b, a, b);
    int j = find(size_b, size_a, b, a);
    dsu.une(a[i], b[j]);
    setRoad(a[i], b[j]);
  }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10