Submission #58604

#	Time	Username	Problem	Language	Result	Execution time	Memory
58604		ruhanhabib39	ICC (CEOI16_icc)	C++17	0 / 100	251 ms	964 KiB

icc

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

// query(|A|,|B|,A,B) (A, B) disjoint, returns whether there's an edge between A, B
// setRoad(u,v) tells there's an edge u--v

namespace {
   const int MAXN = 100;

   int n;
   int par[MAXN + 10];
   vector<vector<int>> comp;

   void init(int n_) {
      n = n_;
      for(int u = 1; u <= n; u++) {
         par[u] = u-1;
         comp.push_back(vector<int>(1, u));
      }
   }

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

   void append(vector<int>& a, const vector<int>& b) {
      a.insert(a.end(), b.begin(), b.end());
   }

   int ask(int st) {
      vector<int> a, b;
      for(int i = 0; i < (int)comp.size(); i++) {
         if((i & st) == st) append(a, comp[i]);
         else append(b, comp[i]);
      }
      return ask(a, b);
   }

   int find_u(vector<int> aa, vector<int> bb) {
      int lo = 0, hi = (int)aa.size() - 1;
      while(lo < hi) {
         int m = (lo + hi) / 2;
         vector<int> a(aa.begin(), aa.begin() + m + 1);
         if(ask(a, bb)) hi = m;
         else lo = m+1;
      }
      return aa[lo];
   }

   ostream& operator<<(ostream& os, vector<int> v) {
      os << "[ ";
      for(int x : v) os << x << " ";
      return os << "]";
   }

   void find_edge() {
      int p = 1;
      while(p <= 100 && !ask(p)) p <<= 1;
      vector<int> aa, bb;
      for(int i = 0; i < (int)comp.size(); i++) {
         if((i & p) == p) append(aa, comp[i]);
         else append(bb, comp[i]);
      }
      cerr << "aa = " << aa << "\n";
      cerr << "bb = " << bb << "\n";
      int u = find_u(aa, bb);
      int v = find_u(bb, aa);
      append(comp[par[u]], comp[par[v]]);
      comp.erase(comp.begin() + par[v]);
      for(int i = 0; i < (int)comp.size(); i++) {
         for(int x : comp[i]) par[x] = i;
      }

      setRoad(u, v);
   }

};

void run(int n) {
   init(n);
   for(int i = 0; i < n-1; i++) {
      find_edge();
   }
}

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