Submission #442387

#	Time	Username	Problem	Language	Result	Execution time	Memory
442387		DmitryGrigorev	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	3 ms	456 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 = 150000;
int N = 10;
int ITER = 100;

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; ++i) {
        guys.pb(undef.back());
        undef.pop_back();
      }

      vector<int> W;
      for (int j = 0; j < (1<<N); ++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; ++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 < mask; ++j) {
        if ((1<<j)&mask) b.pb(guys[j]);
        else a.pb(guys[j]);
      }

    }

  }


}


#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);

}
#endif

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:52:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   while (a.size() < WANT && b.size() < WANT && undef.size()) {
      |          ~~~~~~~~~^~~~~~
mushrooms.cpp:52:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   while (a.size() < WANT && b.size() < WANT && undef.size()) {
      |                             ~~~~~~~~~^~~~~~
mushrooms.cpp:53:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     if (undef.size() < N) {
      |         ~~~~~~~~~~~~~^~~
mushrooms.cpp:131:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |           for (int j = 1; j < arr.size(); ++j) if (arr[j] != arr[j-1]) S++;
      |                           ~~^~~~~~~~~~~~
mushrooms.cpp:149:1: warning: no return statement in function returning non-void [-Wreturn-type]
  149 | }
      | ^

• Subtask 1: 0 / 100