oj.uz

Submission #442457

# Submission time Handle Problem Language Result Execution time Memory
442457 2021-07-07T18:06:02 Z DmitryGrigorev Counting Mushrooms (IOI20_mushrooms) C++14
95.7627 / 100
 1816 ms 1660 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 = 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

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 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 88 ms 1048 KB Output is correct
5 Correct 827 ms 1548 KB Output is correct
6 Correct 1639 ms 1320 KB Output is correct
7 Correct 110 ms 1460 KB Output is correct
8 Correct 109 ms 1416 KB Output is correct
9 Correct 191 ms 1356 KB Output is correct
10 Correct 1006 ms 1636 KB Output is correct
11 Correct 1303 ms 1404 KB Output is correct
12 Correct 999 ms 1408 KB Output is correct
13 Correct 172 ms 1408 KB Output is correct
14 Correct 1417 ms 1424 KB Output is correct
15 Partially correct 1407 ms 1396 KB Output is partially correct
16 Partially correct 1487 ms 1588 KB Output is partially correct
17 Correct 1241 ms 1376 KB Output is correct
18 Correct 301 ms 1392 KB Output is correct
19 Partially correct 1732 ms 1456 KB Output is partially correct
20 Correct 1145 ms 1404 KB Output is correct
21 Correct 1262 ms 1400 KB Output is correct
22 Partially correct 1613 ms 1404 KB Output is partially correct
23 Correct 730 ms 1408 KB Output is correct
24 Correct 1407 ms 1380 KB Output is correct
25 Correct 1316 ms 1444 KB Output is correct
26 Correct 1503 ms 1408 KB Output is correct
27 Correct 1471 ms 1404 KB Output is correct
28 Partially correct 1660 ms 1464 KB Output is partially correct
29 Partially correct 1714 ms 1452 KB Output is partially correct
30 Partially correct 1564 ms 1400 KB Output is partially correct
31 Partially correct 1666 ms 1392 KB Output is partially correct
32 Correct 1503 ms 1456 KB Output is correct
33 Partially correct 1514 ms 1396 KB Output is partially correct
34 Partially correct 1580 ms 1400 KB Output is partially correct
35 Partially correct 1522 ms 1400 KB Output is partially correct
36 Partially correct 1227 ms 1396 KB Output is partially correct
37 Partially correct 1489 ms 1400 KB Output is partially correct
38 Partially correct 1567 ms 1404 KB Output is partially correct
39 Partially correct 1507 ms 1456 KB Output is partially correct
40 Partially correct 1566 ms 1544 KB Output is partially correct
41 Partially correct 1568 ms 1476 KB Output is partially correct
42 Correct 1499 ms 1408 KB Output is correct
43 Partially correct 1387 ms 1460 KB Output is partially correct
44 Partially correct 1536 ms 1396 KB Output is partially correct
45 Partially correct 1816 ms 1408 KB Output is partially correct
46 Correct 1202 ms 1560 KB Output is correct
47 Partially correct 1445 ms 1404 KB Output is partially correct
48 Partially correct 1665 ms 1580 KB Output is partially correct
49 Correct 1369 ms 1456 KB Output is correct
50 Partially correct 1524 ms 1452 KB Output is partially correct
51 Partially correct 1610 ms 1464 KB Output is partially correct
52 Correct 1458 ms 1560 KB Output is correct
53 Partially correct 1661 ms 1404 KB Output is partially correct
54 Partially correct 1435 ms 1660 KB Output is partially correct
55 Partially correct 1377 ms 1396 KB Output is partially correct
56 Partially correct 1671 ms 1540 KB Output is partially correct
57 Partially correct 1535 ms 1504 KB Output is partially correct
58 Partially correct 1404 ms 1464 KB Output is partially correct
59 Correct 1427 ms 1396 KB Output is correct
60 Correct 1167 ms 1508 KB Output is correct
61 Correct 1436 ms 1404 KB Output is correct
62 Correct 1 ms 264 KB Output is correct
63 Correct 1 ms 200 KB Output is correct
64 Correct 1 ms 200 KB Output is correct
65 Correct 0 ms 200 KB Output is correct
66 Correct 1 ms 200 KB Output is correct
67 Correct 1 ms 200 KB Output is correct
68 Correct 1 ms 200 KB Output is correct
69 Correct 0 ms 200 KB Output is correct
70 Correct 0 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 200 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 1 ms 200 KB Output is correct
78 Correct 0 ms 200 KB Output is correct
79 Correct 1 ms 200 KB Output is correct
80 Correct 0 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 1 ms 200 KB Output is correct
84 Correct 0 ms 200 KB Output is correct
85 Correct 1 ms 256 KB Output is correct
86 Correct 1 ms 256 KB Output is correct
87 Correct 1 ms 200 KB Output is correct
88 Correct 1 ms 200 KB Output is correct
89 Correct 0 ms 200 KB Output is correct
90 Correct 0 ms 200 KB Output is correct
91 Correct 0 ms 200 KB Output is correct