oj.uz

Submission #58612

# Submission time Handle Problem Language Result Execution time Memory
58612 2018-07-18T12:26:44 Z ruhanhabib39 ICC (CEOI16_icc) C++17
90 / 100
 215 ms 900 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();
   }
}

Compilation message

icc.cpp:53:13: warning: 'std::ostream& {anonymous}::operator<<(std::ostream&, std::vector<int>)' defined but not used [-Wunused-function]
    ostream& operator<<(ostream& os, vector<int> v) {
             ^~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 98 queries used.
2 Correct 9 ms 616 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 692 KB Ok! 523 queries used.
2 Correct 51 ms 692 KB Ok! 659 queries used.
3 Correct 49 ms 692 KB Ok! 658 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 692 KB Ok! 1406 queries used.
2 Correct 215 ms 692 KB Ok! 1612 queries used.
3 Correct 162 ms 736 KB Ok! 1577 queries used.
4 Correct 175 ms 736 KB Ok! 1484 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 796 KB Ok! 1500 queries used.
2 Correct 189 ms 856 KB Ok! 1485 queries used.
3 Correct 195 ms 856 KB Ok! 1636 queries used.
4 Correct 187 ms 864 KB Ok! 1456 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 864 KB Ok! 1623 queries used.
2 Correct 188 ms 900 KB Ok! 1608 queries used.
3 Correct 166 ms 900 KB Ok! 1668 queries used.
4 Correct 191 ms 900 KB Ok! 1636 queries used.
5 Correct 146 ms 900 KB Ok! 1423 queries used.
6 Correct 178 ms 900 KB Ok! 1530 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 900 KB Too many queries! 1644 out of 1625
2 Halted 0 ms 0 KB -