oj.uz

Submission #442450

# Submission time Handle Problem Language Result Execution time Memory
442450 2021-07-07T18:03:47 Z DmitryGrigorev Counting Mushrooms (IOI20_mushrooms) C++14
95.7627 / 100
 1721 ms 1692 KB 
#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 = 159;
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

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
95.7627 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 92 ms 956 KB Output is correct
5 Correct 851 ms 1312 KB Output is correct
6 Correct 1444 ms 1384 KB Output is correct
7 Correct 136 ms 1428 KB Output is correct
8 Correct 126 ms 1416 KB Output is correct
9 Correct 125 ms 1416 KB Output is correct
10 Correct 1155 ms 1404 KB Output is correct
11 Correct 1349 ms 1468 KB Output is correct
12 Correct 1185 ms 1400 KB Output is correct
13 Correct 147 ms 1416 KB Output is correct
14 Correct 1329 ms 1436 KB Output is correct
15 Correct 1358 ms 1456 KB Output is correct
16 Partially correct 1444 ms 1400 KB Output is partially correct
17 Correct 1067 ms 1380 KB Output is correct
18 Correct 308 ms 1408 KB Output is correct
19 Partially correct 1701 ms 1404 KB Output is partially correct
20 Correct 1004 ms 1396 KB Output is correct
21 Correct 1174 ms 1408 KB Output is correct
22 Partially correct 1476 ms 1512 KB Output is partially correct
23 Correct 607 ms 1456 KB Output is correct
24 Correct 1341 ms 1440 KB Output is correct
25 Correct 1384 ms 1404 KB Output is correct
26 Partially correct 1494 ms 1504 KB Output is partially correct
27 Partially correct 1306 ms 1392 KB Output is partially correct
28 Partially correct 1491 ms 1392 KB Output is partially correct
29 Partially correct 1654 ms 1512 KB Output is partially correct
30 Partially correct 1517 ms 1580 KB Output is partially correct
31 Partially correct 1619 ms 1396 KB Output is partially correct
32 Partially correct 1473 ms 1404 KB Output is partially correct
33 Partially correct 1479 ms 1616 KB Output is partially correct
34 Partially correct 1536 ms 1520 KB Output is partially correct
35 Partially correct 1372 ms 1400 KB Output is partially correct
36 Partially correct 1207 ms 1528 KB Output is partially correct
37 Partially correct 1388 ms 1640 KB Output is partially correct
38 Partially correct 1547 ms 1408 KB Output is partially correct
39 Partially correct 1531 ms 1580 KB Output is partially correct
40 Partially correct 1479 ms 1456 KB Output is partially correct
41 Partially correct 1506 ms 1640 KB Output is partially correct
42 Correct 1422 ms 1396 KB Output is correct
43 Partially correct 1371 ms 1692 KB Output is partially correct
44 Partially correct 1407 ms 1360 KB Output is partially correct
45 Partially correct 1721 ms 1380 KB Output is partially correct
46 Partially correct 1232 ms 1376 KB Output is partially correct
47 Partially correct 1366 ms 1576 KB Output is partially correct
48 Partially correct 1554 ms 1400 KB Output is partially correct
49 Correct 1316 ms 1372 KB Output is correct
50 Partially correct 1534 ms 1644 KB Output is partially correct
51 Partially correct 1594 ms 1456 KB Output is partially correct
52 Partially correct 1484 ms 1552 KB Output is partially correct
53 Partially correct 1547 ms 1512 KB Output is partially correct
54 Partially correct 1437 ms 1500 KB Output is partially correct
55 Correct 1366 ms 1652 KB Output is correct
56 Partially correct 1369 ms 1412 KB Output is partially correct
57 Partially correct 1351 ms 1404 KB Output is partially correct
58 Partially correct 1413 ms 1436 KB Output is partially correct
59 Partially correct 1377 ms 1568 KB Output is partially correct
60 Correct 1182 ms 1452 KB Output is correct
61 Partially correct 1270 ms 1416 KB Output is partially correct
62 Correct 0 ms 200 KB Output is correct
63 Correct 0 ms 200 KB Output is correct
64 Correct 0 ms 200 KB Output is correct
65 Correct 0 ms 200 KB Output is correct
66 Correct 0 ms 200 KB Output is correct
67 Correct 0 ms 200 KB Output is correct
68 Correct 1 ms 200 KB Output is correct
69 Correct 1 ms 200 KB Output is correct
70 Correct 1 ms 200 KB Output is correct
71 Correct 1 ms 200 KB Output is correct
72 Correct 0 ms 200 KB Output is correct
73 Correct 1 ms 256 KB Output is correct
74 Correct 1 ms 200 KB Output is correct
75 Correct 0 ms 200 KB Output is correct
76 Correct 1 ms 200 KB Output is correct
77 Correct 0 ms 200 KB Output is correct
78 Correct 1 ms 200 KB Output is correct
79 Correct 1 ms 200 KB Output is correct
80 Correct 1 ms 200 KB Output is correct
81 Correct 0 ms 200 KB Output is correct
82 Correct 1 ms 200 KB Output is correct
83 Correct 0 ms 200 KB Output is correct
84 Correct 1 ms 200 KB Output is correct
85 Correct 0 ms 200 KB Output is correct
86 Correct 0 ms 200 KB Output is correct
87 Correct 1 ms 200 KB Output is correct
88 Correct 0 ms 200 KB Output is correct
89 Correct 1 ms 200 KB Output is correct
90 Correct 0 ms 200 KB Output is correct
91 Correct 0 ms 200 KB Output is correct