Submission #605177

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
605177	2022-07-25T13:40:07 Z	Sam_a17	Counting Mushrooms (IOI20_mushrooms)	C++14	92.623 / 100	140 ms	1556 KB

mushrooms

#include <bits/stdc++.h>
using namespace std;
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(x) cout << #x << " " << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin());
 
#define pb push_back
#define ld long double
#define ll long long
 
// #include "mushrooms.h"
int use_machine(vector<int> m);
 
void pr(vector<int>& a) {
  cerr << "arr" << " ";
  for(auto i: a) {
    cerr << i << " "; 
  } cerr << endl;
}
 
 
// #include "mushrooms.h"
int use_machine(vector<int> m);

int count_mushrooms(int n) {
  set<int> st;
  for(int i = 0; i < n; i++) {
    st.insert(i);
  }
 
  int answ = 0;
  int kAx = 1, kBx = 0, cnt = 0, qn = 0;
  int lim = 80;
  vector<int> ones, zeroes{0};
  int start = -1;

  for(int i = 1; i < n; i++) {
    vector<int> aski{0, i};
    int s = use_machine(aski);
    if(s == 1) {
      ones.push_back(i);
      kBx++;
    } else {
      zeroes.push_back(i);
      kAx++;
    }
 
    if(kAx >= 2 || kBx >= 2) {
      start = i + 1;
      break;
    }
  }
 
  if(start == -1) {
    return kAx;
  }

  if(kAx >= 2) {
    for(int i = start; i + 1 < n; i += 2) {
      vector<int> ask{0, i, zeroes.back(), i + 1};
      int s = use_machine(ask);
      
      if(s == 0) {
        zeroes.push_back(i);
        zeroes.push_back(i + 1);
      } else if(s == 1) {
        zeroes.push_back(i);
        ones.push_back(i + 1);
      } else if(s == 2) {
        ones.push_back(i);
        zeroes.push_back(i + 1);
      } else {
        ones.push_back(i);
        ones.push_back(i + 1);
      }
      
      //
      kAx = sz(zeroes), kBx = sz(ones);

      if(kAx >= lim || kBx >= lim) {
        start = i + 2;
        break;
      }

      start += 2;
    }
  } else  {
    for(int i = start; i + 1 < n; i += 2) {
      vector<int> ask{ones.front(), i, ones.back(), i + 1};
      int s = use_machine(ask);
      
      if(s == 0) {
        ones.push_back(i);
        ones.push_back(i + 1);
      } else if(s == 1) {
        ones.push_back(i);
        zeroes.push_back(i + 1);
      } else if(s == 2) {
        zeroes.push_back(i);
        ones.push_back(i + 1);
      } else {
        zeroes.push_back(i);
        zeroes.push_back(i + 1);
      }
      
      //
      kAx = sz(zeroes), kBx = sz(ones);
 
      if(kAx >= lim || kBx >= lim) {
        start = i + 2;
        break;
      }

      start += 2;
    }
  }

  // pr(zeroes);
  // pr(ones);
  // dbg(answ)

  int countt = 0;
  while(start < n) {
    kAx = sz(zeroes), kBx = sz(ones);
    // dbg(kAx)
    // dbg(kBx)
    if(kAx > kBx) {
      vector<int> qry;
      for(int j = start, k = 0; j < min(n, start + kAx); j++, k++) {
        qry.push_back(zeroes[k]);
        qry.push_back(j);
      }
 
      if(!qry.empty()) {
        int s = use_machine(qry);
  
        int ci = 0;
        bool flag = false;
        if(s % 2 == 1) {
          s--, ci++;
          ones.push_back(qry.back());
        } else {
          countt++;
          zeroes.push_back(qry.back());
        }

        answ += (sz(qry) / 2 - ci) - (s / 2);
      }
    } else {
      vector<int> qry;
      for(int j = start, k = 0; j < min(n, start + kBx); j++, k++) {
        qry.push_back(ones[k]);
        qry.push_back(j);
      }

      if(!qry.empty()) {
        int s = use_machine(qry);
        pr(qry);
        int ci = 0;

        if(s % 2 == 1) {
          s++, countt++;
          zeroes.push_back(qry.back());
        } else {
          ones.push_back(qry.back());
        }
        // dbg(s)
        answ += (s / 2);
      }
    }

    start += max(kAx, kBx);
  }
  
  return answ + sz(zeroes) - countt;
}

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:142:14: warning: unused variable 'flag' [-Wunused-variable]
  142 |         bool flag = false;
      |              ^~~~
mushrooms.cpp:163:13: warning: unused variable 'ci' [-Wunused-variable]
  163 |         int ci = 0;
      |             ^~
mushrooms.cpp:36:25: warning: unused variable 'cnt' [-Wunused-variable]
   36 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                         ^~~
mushrooms.cpp:36:34: warning: unused variable 'qn' [-Wunused-variable]
   36 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                                  ^~

Subtask #1

92.623 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	312 KB	Output is correct
5	Correct	3 ms	208 KB	Output is correct
6	Correct	2 ms	404 KB	Output is correct
7	Correct	9 ms	1368 KB	Output is correct
8	Correct	12 ms	1256 KB	Output is correct
9	Correct	9 ms	1252 KB	Output is correct
10	Correct	11 ms	1232 KB	Output is correct
11	Partially correct	15 ms	1232 KB	Output is partially correct
12	Correct	113 ms	1440 KB	Output is correct
13	Correct	114 ms	1368 KB	Output is correct
14	Correct	5 ms	720 KB	Output is correct
15	Partially correct	14 ms	1248 KB	Output is partially correct
16	Partially correct	37 ms	1300 KB	Output is partially correct
17	Correct	54 ms	868 KB	Output is correct
18	Correct	115 ms	1372 KB	Output is correct
19	Partially correct	41 ms	1240 KB	Output is partially correct
20	Correct	12 ms	1240 KB	Output is correct
21	Correct	114 ms	1416 KB	Output is correct
22	Partially correct	109 ms	1444 KB	Output is partially correct
23	Correct	9 ms	1232 KB	Output is correct
24	Correct	56 ms	804 KB	Output is correct
25	Partially correct	12 ms	1256 KB	Output is partially correct
26	Partially correct	125 ms	1484 KB	Output is partially correct
27	Partially correct	9 ms	1256 KB	Output is partially correct
28	Partially correct	111 ms	1448 KB	Output is partially correct
29	Partially correct	96 ms	1408 KB	Output is partially correct
30	Partially correct	38 ms	1344 KB	Output is partially correct
31	Partially correct	17 ms	1284 KB	Output is partially correct
32	Partially correct	15 ms	1384 KB	Output is partially correct
33	Partially correct	111 ms	1428 KB	Output is partially correct
34	Partially correct	22 ms	1256 KB	Output is partially correct
35	Partially correct	116 ms	1384 KB	Output is partially correct
36	Partially correct	108 ms	1436 KB	Output is partially correct
37	Partially correct	111 ms	1412 KB	Output is partially correct
38	Partially correct	24 ms	1284 KB	Output is partially correct
39	Partially correct	12 ms	1276 KB	Output is partially correct
40	Partially correct	38 ms	1284 KB	Output is partially correct
41	Partially correct	112 ms	1328 KB	Output is partially correct
42	Partially correct	96 ms	1556 KB	Output is partially correct
43	Partially correct	133 ms	1432 KB	Output is partially correct
44	Partially correct	11 ms	1284 KB	Output is partially correct
45	Partially correct	27 ms	1232 KB	Output is partially correct
46	Partially correct	34 ms	1300 KB	Output is partially correct
47	Partially correct	100 ms	1304 KB	Output is partially correct
48	Partially correct	28 ms	1272 KB	Output is partially correct
49	Partially correct	65 ms	1264 KB	Output is partially correct
50	Partially correct	78 ms	1448 KB	Output is partially correct
51	Partially correct	110 ms	1392 KB	Output is partially correct
52	Partially correct	101 ms	1360 KB	Output is partially correct
53	Partially correct	16 ms	1276 KB	Output is partially correct
54	Partially correct	99 ms	1356 KB	Output is partially correct
55	Partially correct	69 ms	1264 KB	Output is partially correct
56	Partially correct	119 ms	1420 KB	Output is partially correct
57	Partially correct	135 ms	1396 KB	Output is partially correct
58	Partially correct	61 ms	1472 KB	Output is partially correct
59	Partially correct	140 ms	1348 KB	Output is partially correct
60	Partially correct	30 ms	1276 KB	Output is partially correct
61	Partially correct	104 ms	1432 KB	Output is partially correct
62	Correct	0 ms	208 KB	Output is correct
63	Correct	1 ms	240 KB	Output is correct
64	Correct	0 ms	208 KB	Output is correct
65	Correct	0 ms	208 KB	Output is correct
66	Correct	1 ms	208 KB	Output is correct
67	Correct	1 ms	208 KB	Output is correct
68	Correct	1 ms	208 KB	Output is correct
69	Correct	0 ms	208 KB	Output is correct
70	Correct	1 ms	208 KB	Output is correct
71	Correct	0 ms	208 KB	Output is correct
72	Correct	1 ms	208 KB	Output is correct
73	Correct	0 ms	208 KB	Output is correct
74	Correct	1 ms	208 KB	Output is correct
75	Correct	0 ms	208 KB	Output is correct
76	Correct	0 ms	208 KB	Output is correct
77	Correct	0 ms	208 KB	Output is correct
78	Correct	0 ms	208 KB	Output is correct
79	Correct	1 ms	208 KB	Output is correct
80	Correct	1 ms	208 KB	Output is correct
81	Correct	1 ms	208 KB	Output is correct
82	Correct	1 ms	208 KB	Output is correct
83	Correct	1 ms	208 KB	Output is correct
84	Correct	0 ms	208 KB	Output is correct
85	Correct	0 ms	208 KB	Output is correct
86	Correct	0 ms	208 KB	Output is correct
87	Correct	0 ms	208 KB	Output is correct
88	Correct	0 ms	208 KB	Output is correct
89	Correct	1 ms	208 KB	Output is correct
90	Correct	0 ms	208 KB	Output is correct
91	Correct	1 ms	208 KB	Output is correct