Submission #116680

#	Time	Username	Problem	Language	Result	Execution time	Memory
116680		IOrtroiii	ICC (CEOI16_icc)	C++14	100 / 100	142 ms	640 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

const int N = 105;

int qa[N], qb[N];

int query(vector<int> a, vector<int> b) {
   int sza = a.size(), szb = b.size();
   for (int i = 0; i < sza; ++i) {
      qa[i] = a[i];
   }
   for (int i = 0; i < szb; ++i) {
      qb[i] = b[i];
   }
   return query(sza, szb, qa, qb);
}

int fnd(vector<int> from, vector<int> to) {
   int l = 0, r = from.size() - 1;
   while (l < r) {
      int md = (l + r) >> 1;
      if (query(vector<int>(from.begin(), from.begin() + md + 1), to)) {
         r = md;
      } else {
         l = md + 1;
      }
   }
   return from[l];
}

int p[N];
vector<int> comp[N];

int getp(int u) {
   if (p[u] == u) {
      return u;
   } else {
      return p[u] = getp(p[u]);
   }
}

void mrg(int u, int v) {
   u = getp(u), v = getp(v);
   if (comp[u].size() < comp[v].size()) {
      swap(u, v);
   }
   p[v] = u;
   for (int w : comp[v]) {
      comp[u].push_back(w);
   }
}

void modify(vector<int> l, vector<int> r) {
   int u = fnd(l, r);
   int v = fnd(r, l);
   mrg(u, v);
   setRoad(u, v);
}

int n;

void solve() {
   vector<int> roots;
   for (int i = 1; i <= n; ++i) {
      if (p[i] == i) {
         roots.push_back(i);
      }
   }
   shuffle(roots.begin(), roots.end(), mt19937(10072002));
   int sz = roots.size();
   for (int i = 0; (1 << i) < sz; ++i) {
      vector<int> l, r;
      for (int j = 0; j < sz; ++j) {
         if (j & (1 << i)) {
            for (int v : comp[roots[j]]) {
               l.push_back(v);
            }
         } else {
            for (int v : comp[roots[j]]) {
               r.push_back(v);
            }
         }
      }
      if (query(l, r)) {
         modify(l, r);
         return;
      }
   }
}

void run(int n) {
   ::n = n;
   for (int i = 1; i <= n; ++i) {
      p[i] = i;
      comp[i].push_back(i);
   }
   for (int i = 0; i < n - 1; ++i) {
      solve();
   }
}

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