Submission #1086439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086439		juicy	ICC (CEOI16_icc)	C++17	100 / 100	97 ms	856 KiB

icc

#include "icc.h"
 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

template<class T>
ostream &operator << (ostream &os, vector<T> a) {
  os << "{";
  for (int i = 0; i < a.size(); ++i) {
    os << (i ? ", " : "") << a[i];
  }
  return os << "}";
}

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) {
  if (a.size() == 1) {
    return a[0];
  }
  int m = a.size() / 2;
  auto lt = vector(a.begin(), a.begin() + m), rt = vector(a.begin() + m, a.end());
  return qry(lt, b) ? find(lt, b) : find(rt, b);
}
 
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);
      }
    }
    int m = root.size();
    int x = 0, k = -1;
    for (int i = 0; 1 << i < m; ++i) {
      vector<int> a, 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)) {
        x ^= 1 << i;
        k = i;
      }
    }
    int y = 0;
    for (int i = 0; 1 << i < m; ++i) {
      if (i == k) {
        continue;
      }
      vector<int> a, b;
      for (int j = 0; j < m; ++j) {
        auto &v = j & (1 << i | 1 << k) ? a : b;
        v.insert(v.end(), ver[root[j]].begin(), ver[root[j]].end());
      }
      if (!qry(a, b)) {
        y ^= 1 << i;
      }
    }
    x ^= y;
    int u = find(ver[root[x]], ver[root[y]]), v = find(ver[root[y]], ver[root[x]]);
    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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10