oj.uz

Submission #58611

# Submission time Handle Problem Language Result Execution time Memory
58611 2018-07-18T12:24:00 Z ruhanhabib39 ICC (CEOI16_icc) C++17
0 / 100
 285 ms 952 KB 
#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_;
      comp = vector<vector<int>>();
      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 << "]";
   }


   bool good(vector<int> a, vector<int> b) {
      for(int x : a) {
         if(count(b.begin(), b.end(), x)) return false;
      }
      return true;
   }

   void find_edge() {
      int p = 1;
      while(!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]);
      }
      assert(good(aa, bb));
      cerr << "aa = " << aa << "\n";
      cerr << "bb = " << bb << "\n";
      int u = find_u(aa, bb);
      int v = find_u(bb, aa);
      assert(par[u] != par[v]);
      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.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 504 KB Program is not terminated properly.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 616 KB Program is not terminated properly.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 688 KB Program is not terminated properly.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 740 KB Program is not terminated properly.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 952 KB Program is not terminated properly.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 285 ms 952 KB Program is not terminated properly.
2 Halted 0 ms 0 KB -