Submission #605848

#	Time	Username	Problem	Language	Result	Execution time	Memory
605848		juancarlovieri	ICC (CEOI16_icc)	C++17	100 / 100	135 ms	620 KiB

icc

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

int par[105];
vector<int> all[105];
int aarr[105];
int barr[105];
int cnt2;

int* conv(vector<int> x, int* a) {
  for (int i = 0; i < x.size(); ++i) a[i] = x[i];
  return a;
}

int tanya (vector<int> a, vector<int> b) {
  vector<int> aa;
  vector<int> bb;
  for (auto i : a) {
    for (auto j : all[i]) aa.push_back(j + 1);
  }
  for (auto i : b) {
    for (auto j : all[i]) bb.push_back(j + 1);
  }
  ++cnt2;
  if (cnt2 > 2250) while (1);
  return query(aa.size(), bb.size(), conv(aa, aarr), conv(bb, barr));
}

int find(int i) {
  if (par[i] == i) return i;
  return par[i] = find(par[i]);
}

pair<vector<int>, vector<int>> div(vector<int> x) {
  vector<int> a, b;
  for (int i = 0; i < x.size() / 2; ++i) a.push_back(x[i]);
  for (int i = x.size() / 2; i < x.size(); ++i) b.push_back(x[i]);
  return {a, b};
}

pair<int, int> ans;

int tanya2(vector<int> a, vector<int> b) {
  for (auto& i : a) ++i;
  for (auto& i : b) ++i;
  ++cnt2;
  if (cnt2 > 2250) while (1);
  return query(a.size(), b.size(), conv(a, aarr), conv(b, barr));
}

bool cari(vector<int> act) {
  if (act.size() == 1) return 0;
  // puts("TSE");
  auto [a, b] = div(act);
  while (tanya(a, b) == 0) {
    random_shuffle(act.begin(), act.end());
    a = div(act).first;
    b = div(act).second;
  }
  // if (tanya(a, b)) {
  vector<int> na, nb;
  for (auto i : a) {
    for (auto j : all[i]) na.push_back(j);
  }
  for (auto i : b) {
    for (auto j : all[i]) nb.push_back(j);
  }
  a = na, b = nb;
  while (a.size() > 1) {
    auto [a1, a2] = div(a);

    // for (auto i : a1) cout << i << ' ';
    //   cout << endl;
    // for (auto i : b) cout << i << ' ';
    //   cout << endl;
    if (tanya2(a1, b)) a = a1;
    else a = a2;
  }
  while (b.size() > 1) {
    auto [b1, b2] = div(b);
    if (tanya2(a, b1)) b = b1;
    else b = b2;
  }
  ans = {find(a[0]), find(b[0])};
  // while(a.size() > 1) {
  //   auto [a1, a2] = div(a);
  //   if (tanya(a1, b)) a = a1;
  //   else a = a2;
  // }
  // while(b.size() > 1) {
  //   auto [b1, b2] = div(b);
  //   if (tanya(a, b1)) b = b1;
  //   else b = b2;
  // }
  // ans = {a[0], b[0]};
  // // cout << a[0] << ' ' << b[0] << endl;
  // a = all[a[0]];
  // b = all[b[0]];

  // // for (auto i : a) cout << i << ' ';
  // //   cout << endl;
  // // for (auto i : b) cout << i << ' ';
  // //   cout << endl;
  // while(a.size() > 1) {
  //   auto [a1, a2] = div(a);

  // // for (auto i : a1) cout << i << ' ';
  // //   cout << endl;
  // // for (auto i : b) cout << i << ' ';
  // //   cout << endl;
  //   if (tanya2(a1, b)) a = a1;
  //   else a = a2;
  // }
  // while(b.size() > 1) {
  //   auto [b1, b2] = div(b);
  //   if (tanya2(a, b1)) b = b1;
  //   else b = b2;
  // }


  setRoad(a[0] + 1, b[0] + 1);
  return 1;
  // } else {
  //   if (cari(a)) return 1;
  //   if (cari(b)) return 1;
  // }
  return 0;
}

void run(int n) {
  srand(time(0));
  // query(1, 1, {}, {});
  iota(par, par + n, 0);
  vector<int> act(n);
  iota(act.begin(), act.end(), 0);
  for (int i = 0; i < n; ++i) all[i].push_back(i);
  for (int ii = 0; ii < n - 1; ++ii) {
    random_shuffle(act.begin(), act.end());
    // cout << "FINDING NEW " << ii << endl;
    // assert(cari(act));

    // for (auto i : all[ans.second]) {
    //   all[ans.first].push_back(i);
    // }
    // par[ans.second] = ans.first;
    // act.clear();
    // for (int i = 0; i < n; ++i) if (find(i) == i) act.push_back(i);
    // for (auto i : act) {
    //   for (auto j : all[i])
    //     cout << j << ' ';
    // cout << endl;
    // }
    int tmp = 0;
    int sukses = -1;
    for (int i = 0; i < 20; ++i) {
      if ((1 << i) > act.size()) break;
      vector<int> a, b;
      for (int j = 0; j < act.size(); ++j) {
        if (j & (1 << i)) b.push_back(act[j]);
        else a.push_back(act[j]);
      }
      if (a.empty() or b.empty()) continue;
      // for (auto i : a) {
      //   cout << i << ' ';
      // }
      // cout << endl;
      // for (auto i : b) {
      //   cout << i << ' ';
      // }
      // cout << endl;
      if (tanya(a, b)) {
        sukses = i;
        // cout << i << endl;
        tmp |= (1 << i);
      }
    }
    // cout << sukses << endl;
    vector<int> a, b;

    for (int j = 0; j < act.size(); ++j) {
      if (j & (1 << sukses)) b.push_back(act[j]);
      else a.push_back(act[j]);
    }
    vector<int> na, nb;
    for (auto i : a) {
      for (auto j : all[i]) na.push_back(j);
    }
    for (auto i : b) {
      for (auto j : all[i]) nb.push_back(j);
    }


    if (na.size() > nb.size()) swap(na, nb), swap(a, b);
    while (na.size() > 1) {
      auto [na1, na2] = div(na);
      if (tanya2(na1, nb)) {
        na = na1;
      } else na = na2;
    }
    int idx = -1;
    ans = {find(na[0]), tmp ^ find(na[0])};
    for (int i = 0; i < act.size(); ++i) if (act[i] == find(na[0])) ans.second = act[tmp ^ i];
    for (auto i : all[ans.second]) all[ans.first].push_back(i);
    par[ans.second] = ans.first;
    nb.clear();
    for (auto i : all[ans.second]) nb.push_back(i);
    // for (auto i : na) cout << i << ' ';
    //   cout << endl;
    // for (auto i : nb) cout << i << ' ';
    //   cout << endl;

    while (nb.size() > 1) {
      auto [nb1, nb2] = div(nb);
      if (tanya2(na, nb1)) {
        nb = nb1;
      } else nb = nb2;
    }
    assert(tanya2(na, nb));
    setRoad(na[0] + 1, nb[0] + 1);
    act.clear();
    for (int i = 0; i < n; ++i) if (find(i) == i) act.push_back(i);
  }
}

Compilation message (stderr)

icc.cpp: In function 'int* conv(std::vector<int>, int*)':
icc.cpp:12:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   for (int i = 0; i < x.size(); ++i) a[i] = x[i];
      |                   ~~^~~~~~~~~~
icc.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > div(std::vector<int>)':
icc.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int i = 0; i < x.size() / 2; ++i) a.push_back(x[i]);
      |                   ~~^~~~~~~~~~~~~~
icc.cpp:38:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i = x.size() / 2; i < x.size(); ++i) b.push_back(x[i]);
      |                              ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:157:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |       if ((1 << i) > act.size()) break;
      |           ~~~~~~~~~^~~~~~~~~~~~
icc.cpp:159:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |       for (int j = 0; j < act.size(); ++j) {
      |                       ~~^~~~~~~~~~~~
icc.cpp:181:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for (int j = 0; j < act.size(); ++j) {
      |                     ~~^~~~~~~~~~~~
icc.cpp:203:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     for (int i = 0; i < act.size(); ++i) if (act[i] == find(na[0])) ans.second = act[tmp ^ i];
      |                     ~~^~~~~~~~~~~~
icc.cpp:201:9: warning: unused variable 'idx' [-Wunused-variable]
  201 |     int idx = -1;
      |         ^~~

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