Submission #442395

#	Time	Username	Problem	Language	Result	Execution time	Memory
442395		DmitryGrigorev	Counting Mushrooms (IOI20_mushrooms)	C++14	89.33 / 100	1142 ms	576 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

const int mod = 1000000007;

void add(int& a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}

int mult(int a, int b) {
  return a * (ll)b % mod;
}

int bp(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}

int WANT = 170;
int N = 12;
int ITER = 200;

#ifdef LOCAL
  
int Z = 100;
vector<int> t(Z);

int use_machine(vector<int> req) {
  int ans = 0;
  for (int i = 1; i < req.size(); ++i) if (t[req[i]] != t[req[i-1]]) ans++;
  return ans;
}

#endif

int count_mushrooms(int n) {

  srand(time(0));

  vector<int> a, b, undef;
  a.pb(0);

  for (int i = 1; i < n; ++i) undef.pb(i);
  vector<int> v;
  for (int i = 0; i < N; ++i) v.pb(i);

  random_shuffle(all(undef));

  while (a.size() < WANT && b.size() < WANT && undef.size()) {
    if (undef.size() < N) {
      int lt = undef.back();
      undef.pop_back();

      vector<int> req = {a[0], lt};
      int res = use_machine(req);
      if (res == 0) a.pb(lt);
      else b.pb(lt);
    } 

    else {
      vector<int> guys;
      for (int i = 0; i < N - 1; ++i) {
        guys.pb(undef.back());
        undef.pop_back();
      }

      vector<int> W;
      for (int j = 0; j < (1<<(N-1)); ++j) W.pb(j);

      while (W.size() != 1) {
        int bans = W.size();
        vector<int> best_x = {};
        int our_cost;

        for (int a = 0; a < ITER || best_x.size() == 0; ++a) {
          random_shuffle(all(v));
          auto perm = v;

          vector<int> cnt(20, 0);
          int T = 0;

          for (auto i : W) {
            vector<int> arr;

            int last = -1;
            int S = 0;

            for (int j = 0; j < N; ++j) {
              int nn;
              if (perm[j] == N-1) nn = 0;
              else if ((1<<perm[j])&i) nn=1;
              else nn=0;

              if (nn!=last && last!=-1) S++;
              last = nn;

            }
            
            cnt[S]++;
            T = max(T, cnt[S]);
          }

          if (T < bans) {
            bans = T;
            best_x = perm;
          }

        }

        vector<int> req;
        for (auto el : best_x) {
          if (el == N-1) req.pb(a[0]);
          else req.pb(guys[el]);
        }

        our_cost = use_machine(req);

        vector<int> tt;

        for (auto i : W) {
          vector<int> arr;
          for (int j = 0; j < N; ++j) {
            if (best_x[j] == N-1) arr.pb(0);
            else if ((1<<best_x[j])&i) arr.pb(1);
            else arr.pb(0);
          }
          int S = 0;
          for (int j = 1; j < arr.size(); ++j) if (arr[j] != arr[j-1]) S++;
          if (S == our_cost) tt.pb(i);
        }

        W=tt;
      }

      int mask = W[0];
      for (int j = 0; j < N-1; ++j) {
        if ((1<<j)&mask) b.pb(guys[j]);
        else a.pb(guys[j]);
      }

    }

  }

  int sum = 0;

  while (undef.size()) {
    if (a.size() > b.size()) {
      vector<int> req;
      int u1 = 0;
      int pos = 0;

      while (true) {
        if (pos == 0) {
          if (u1 == a.size()) break;
          else {
            req.pb(a[u1++]);
          }
        }
        else {
          if (!undef.size()) break;
          req.pb(undef.back());
          undef.pop_back();
        }
        pos ^= 1;
      }

      sum += (req.size() - 1 - use_machine(req) + 1) / 2;

    }

    else {
      vector<int> req;
      int u1 = 0;
      int pos = 0;

      while (true) {
        if (pos == 0) {
          if (u1 == b.size()) break;
          else {
            req.pb(b[u1++]);
          }
        }
        else {
          if (!undef.size()) break;
          req.pb(undef.back());
          undef.pop_back();
        }
        pos ^= 1;
      }
      sum += (use_machine(req) + 1) / 2;
    }

  }

  return a.size() + sum;


}


#ifdef LOCAL
int main(){
	freopen("C_input.txt", "r", stdin);
	//freopen("C_output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);

  while (true) {

    t[0] = 0;
    for (int i = 1; i < Z; ++i) t[i] = rand()%2;
    int R = count_mushrooms(Z);

    int tot = 0;
    for (auto x : t) if (x==0) tot++;

    cout << tot << " " << R << endl;

    assert(tot==R);

  }

}
#endif

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:65:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |   while (a.size() < WANT && b.size() < WANT && undef.size()) {
      |          ~~~~~~~~~^~~~~~
mushrooms.cpp:65:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |   while (a.size() < WANT && b.size() < WANT && undef.size()) {
      |                             ~~~~~~~~~^~~~~~
mushrooms.cpp:66:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     if (undef.size() < N) {
      |         ~~~~~~~~~~~~~^~~
mushrooms.cpp:144:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |           for (int j = 1; j < arr.size(); ++j) if (arr[j] != arr[j-1]) S++;
      |                           ~~^~~~~~~~~~~~
mushrooms.cpp:171:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |           if (u1 == a.size()) break;
      |               ~~~^~~~~~~~~~~
mushrooms.cpp:195:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |           if (u1 == b.size()) break;
      |               ~~~^~~~~~~~~~~

• Subtask 1: 89.3281 / 100