Submission #442454

#	Time	Username	Problem	Language	Result	Execution time	Memory
442454		DmitryGrigorev	Counting Mushrooms (IOI20_mushrooms)	C++14	94.17 / 100	1748 ms	1640 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 = 169;
int N = 18;
int ITER = 40;
 
#ifdef LOCAL
 
 
int Z = 20000;
vector<int> t(Z);
int cnt;
 
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++;
  cnt++;
  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);
 
      int oper = 0;

      bool start = true;
 
      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) {
          if (start) {
            for (int i = 0; i < v.size(); ++i) best_x.pb(i);
            start = false;
            break;
          }

          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;
 
          int last = -1;
          int S = 0;
 
          for (int j = 0; j < N; ++j) {
            int nn;
            if (best_x[j] == N-1) nn = 0;
            else if ((1<<best_x[j])&i) nn=1;
            else nn=0;
 
            if (nn!=last && last!=-1) S++;
            last = nn;
 
          }
          
          if (S==our_cost) tt.pb(i);
        }

        W=tt;
        oper++;
      }
 
      //cout << oper << endl;
 
      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;
    cnt=0;
    int R = count_mushrooms(Z);
 
    int tot = 0;
    for (auto x : t) if (x==0) tot++;
  
    assert(tot==R);
    cout << cnt << endl;
 
  }
 
}
#endif

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:68:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   while (a.size() < WANT && b.size() < WANT && undef.size()) {
      |          ~~~~~~~~~^~~~~~
mushrooms.cpp:68:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   while (a.size() < WANT && b.size() < WANT && undef.size()) {
      |                             ~~~~~~~~~^~~~~~
mushrooms.cpp:69:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     if (undef.size() < N) {
      |         ~~~~~~~~~~~~~^~~
mushrooms.cpp:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for (int i = 0; i < v.size(); ++i) best_x.pb(i);
      |                             ~~^~~~~~~~~~
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 == a.size()) break;
      |               ~~~^~~~~~~~~~~
mushrooms.cpp:219:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |           if (u1 == b.size()) break;
      |               ~~~^~~~~~~~~~~

• Subtask 1: 94.1667 / 100