oj.uz

Submission #570326

# Submission time Handle Problem Language Result Execution time Memory
570326 2022-05-29T08:36:54 Z 600Mihnea ICC (CEOI16_icc) C++17
100 / 100
 159 ms 588 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

///mt19937 rng((long long) (new char));

mt19937 rng(228);

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

vector<int> operator + (vector<int> a, vector<int> b) {
  for (auto &x : b) {
    a.push_back(x);
  }
  return a;
}

const int N = 100 + 7;
int t[N];

int get_root(int a) {
  if (t[a] == a) {
    return a;
  } else {
    return t[a] = get_root(t[a]);
  }
}

void join(int a, int b) {
  t[get_root(a)] = get_root(b);
}

void run(int n) {
  for (int i = 1; i <= n; i++) {
    t[i] = i;
  }
  for (int step = 1; step <= n - 1; step++) {
    vector<vector<int>> comps;
    for (int i = 1; i <= n; i++) {
      if (get_root(i) == i) {
        vector<int> currentComp;
        for (int j = 1; j <= n; j++) {
          if (get_root(j) == i) {
            currentComp.push_back(j);
          }
        }
        comps.push_back(currentComp);
      }
    }

    assert((int) comps.size() == n - step + 1);
    assert((int) comps.size() >= 2);

    shuffle(comps.begin(), comps.end(), rng);
    for (auto &comp : comps) {
      shuffle(comp.begin(), comp.end(), rng);
    }

    int MaxValue = (int) comps.size() - 1, Xor = 0;

    for (int bit = 0; (1 << bit) <= MaxValue; bit++) {
      vector<int> have, have_nots;
      for (int i = 0; i < (int) comps.size(); i++) {
        if (i & (1 << bit)) {
          have = have + comps[i];
        } else {
          have_nots = have_nots + comps[i];
        }
      }
      if (get(have, have_nots) == 1) {
        Xor += (1 << bit);
      }
    }

    assert(Xor > 0);

    int id_a = 0, id_b = 0, the_bit = -1;

    for (int bit = 0; (1 << bit) <= MaxValue; bit++) {
      if (Xor & (1 << bit)) {
        the_bit = bit;
      }
    }

    id_a = (1 << the_bit);

    assert(the_bit != -1);


    for (int bit = 0; (1 << bit) <= MaxValue; bit++) {
      if (bit == the_bit) {
        continue;
      }
      if (Xor & (1 << bit)) {
        vector<int> first, second;
        for (int i = 0; i < (int) comps.size(); i++) {
          int la_bit = !!(i & (1 << bit)), la_the = !!(i & (1 << the_bit));
          if (la_bit == 1 && la_the == 1) {
            first = first + comps[i];
          }
          if (la_bit == 0 && la_the == 0) {
            second = second + comps[i];
          }
        }
        if (get(first, second)) {
          id_a += (1 << bit);
        } else {
          id_b += (1 << bit);
        }
      } else {
        vector<int> first, second;
        for (int i = 0; i < (int) comps.size(); i++) {
          int la_bit = !!(i & (1 << bit)), la_the = !!(i & (1 << the_bit));
          if (la_bit == 0 && la_the == 1) {
            first = first + comps[i];
          }
          if (la_bit == 0 && la_the == 0) {
            second = second + comps[i];
          }
        }
        if (!get(first, second)) {
          id_a += (1 << bit);
          id_b += (1 << bit);
        } else {

        }
      }
    }


    assert((id_a ^ id_b) == Xor);
    assert(0 <= id_a && id_a < (int) comps.size());
    assert(0 <= id_b && id_b < (int) comps.size());
    /**for (auto &foo : comps) {
      cout << " ---> ";
      for (auto &x : foo) {
        cout << x << " ";
      }
      cout << "\n";
    }
    cout << id_a << " and " << id_b << "\n";**/
 ///   cout << id_a << " and " << id_b << "\n";
  ///  cout << (int) comps[id_a].size() << " and " << (int) comps[id_b].size() << "\n";

    auto p1 = comps[id_a];
    auto p2 = comps[id_b];

 ///   cout << (int) p1.size() << " and " << (int) p2.size() << "\n";

    while ((int) p1.size() > 1 || (int) p2.size() > 1) {
      shuffle(p1.begin(), p1.end(), rng);
      shuffle(p2.begin(), p2.end(), rng);
      if ((int) p2.size() < (int) p1.size()) {
        swap(p1, p2);
      }
      assert((int) p1.size() <= (int) p2.size());
      vector<int> X(p2.begin(), p2.begin() + (int)p2.size() / 2), Y(p2.begin() + (int) p2.size() / 2, p2.end());
      assert((int) X.size() + (int) Y.size() == (int) p2.size());
      if (get(p1, X)) {
        p2 = X;
      } else {
        p2 = Y;
      }
    }
    assert((int) p1.size() == 1 && (int) p2.size() == 1);
    join(p1[0], p2[0]);
    setRoad(p1[0], p2[0]);
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Ok! 115 queries used.
2 Correct 6 ms 468 KB Ok! 115 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 468 KB Ok! 650 queries used.
2 Correct 44 ms 512 KB Ok! 531 queries used.
3 Correct 38 ms 468 KB Ok! 613 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 536 KB Ok! 1601 queries used.
2 Correct 114 ms 468 KB Ok! 1301 queries used.
3 Correct 121 ms 536 KB Ok! 1605 queries used.
4 Correct 122 ms 528 KB Ok! 1578 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 528 KB Ok! 1575 queries used.
2 Correct 135 ms 528 KB Ok! 1587 queries used.
3 Correct 122 ms 528 KB Ok! 1585 queries used.
4 Correct 124 ms 536 KB Ok! 1601 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 468 KB Ok! 1543 queries used.
2 Correct 138 ms 536 KB Ok! 1522 queries used.
3 Correct 115 ms 536 KB Ok! 1430 queries used.
4 Correct 123 ms 468 KB Ok! 1562 queries used.
5 Correct 131 ms 588 KB Ok! 1594 queries used.
6 Correct 119 ms 524 KB Ok! 1558 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 540 KB Ok! 1552 queries used.
2 Correct 159 ms 532 KB Ok! 1391 queries used.