Submission #699790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
699790	2023-02-18T03:15:33 Z	cig32	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	9 ms	464 KB

mushrooms

#include "bits/stdc++.h"
#include "mushrooms.h"
using namespace std;

int count_mushrooms(int n);

int use_machine(std::vector<int> x);

mt19937_64 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng);
  return u;
}

vector<int> aa, bb;
int idx;

int count_mushrooms(int n) {

  if(n <= 226) {
    int ans = 1;
    for(int i=1; i<n; i++) ans += 1 - use_machine({0, i});
    return ans;
  }

  int ans = 0;
  int type[n];
  for(int i=0; i<n; i++) type[i] = -1;
  type[0] = 0;
  vector<int> list[2];
  list[0].push_back(0);

  
  for(int i=1; i<=2; i++) {
    type[i] = use_machine({0, i});
    list[type[i]].push_back(i);
  }

  vector<int> ind;
  if(list[0].size() > 1) ind = {list[0][0], list[0][1]};
  else ind = {list[1][0], list[1][1]};
  int id;
  if(list[0].size() > list[1].size()) id = 0;
  else id = 1;

  int sigh = use_machine({ind[0], 3, ind[1], 4});
  if(sigh >= 2) type[3] = 1-id;
  else type[3] = id;
  if(sigh % 2 == 1) type[4] = 1-id;
  else type[4] = id;

  list[type[3]].push_back(3);
  list[type[4]].push_back(4);

  ind.clear();
  if(list[0].size() > 2) ind = {list[0][0], list[0][1], list[0][2]};
  else ind = {list[1][0], list[1][1], list[1][2]};
  if(list[0].size() > list[1].size()) id = 0;
  else id = 1;

  int reference = 199;
  for(int i=5; i<=reference-5; i+=5) {
    int res = use_machine({ind[0], i, ind[1], i+1, ind[2], i+2});
    if(res & 1) type[i+2] = 1-id;
    else type[i+2] = id;
    if(res / 2 == 0) {
      type[i] = type[i+1] = id;
      for(int j=i; j<i+3; j++) list[type[j]].push_back(j);
      i -= 2;
      continue;
    }
    else if(res / 2 == 2) {
      type[i] = type[i+1] = 1-id;
      for(int j=i; j<i+3; j++) list[type[j]].push_back(j);
      i -= 2;
      continue;
    }
    else {
      if(list[1-id].size() < 2) {
        
        for(int j=i; j<=i+3; j+=3) {
          res = use_machine({ind[0], j, ind[1], j+1});
          if(res & 1) type[j+1] = 1-id;
          else type[j+1] = id;
          if(res >= 2) type[j] = 1-id;
          else type[j] = id;
        }
        for(int j=i; j<i+5; j++) list[type[j]].push_back(j);
        continue;
      }
      res = use_machine({list[1-id][0], i, list[1-id][1], ind[0], i+1, ind[1], i+3, ind[2], i+4}) - 1;
      if(res & 1) type[i+4] = 1-id;
      else type[i+4] = id;

      
      res -= res%2;
      if(res % 4 == 2) type[i+3] = 1-id;
      else type[i+3] = id;
      
      if(res / 4 == 1) type[i] = id, type[i+1] = 1-id;
      else type[i] = 1-id, type[i+1] = id;
      
    }
    for(int j=i; j<i+5; j++) if(type[j] >= 0) list[type[j]].push_back(j);
  }
  queue<int> qq;
  for(int i=0; i<reference; i++) {
    if(type[i] == -1) {
      qq.push(i);
    }
  }
  while(qq.size() > 1) {
    int f1 = qq.front();qq.pop();
    int f2 = qq.front();qq.pop();
    int res=  use_machine({ind[0], f1, ind[1], f2});
    if(res >= 2) type[f1] = 1-id;
    else type[f1] = id;
    if(res & 1) type[f2] = 1-id;
    else type[f2] = id;
    list[type[f1]].push_back(f1);
    list[type[f2]].push_back(f2);
  }
  if(qq.size() == 1) {
    int f = qq.front();
    type[f] = use_machine({0, f});
    list[type[f]].push_back(f);
  }
  ans = list[0].size(); 
  queue<int> q;
  
  for(int i=reference; i<n; i++) q.push(i);
  while(q.size()) {
    int maa = max(list[0].size(), list[1].size());
    int idx;
    if(list[0].size() > list[1].size()) idx = 0;
    else idx = 1;
    vector<int> toask;
    maa = min(maa, (int) q.size());
    for(int i=0; i<maa; i++) {
      toask.push_back(list[idx][i]);
      toask.push_back(q.front());
      q.pop();
    }
    int res = use_machine(toask);
    if(res & 1) {
      if(idx == 0) {
        list[1].push_back(toask.back());
      }
      else {
        list[0].push_back(toask.back());
      }
    }
    else {
      if(idx == 0) {
        list[0].push_back(toask.back());
      }
      else {
        list[1].push_back(toask.back());
      }
    }
    if(idx == 0) res = maa - (res+1)/2;
    else res = (res+1)/2;
    ans += res;
  }
  
  
  return ans;

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	0 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	2 ms	208 KB	Output is correct
6	Correct	2 ms	208 KB	Output is correct
7	Correct	5 ms	424 KB	Output is correct
8	Correct	6 ms	464 KB	Output is correct
9	Correct	5 ms	464 KB	Output is correct
10	Correct	6 ms	464 KB	Output is correct
11	Correct	6 ms	464 KB	Output is correct
12	Correct	7 ms	464 KB	Output is correct
13	Correct	7 ms	380 KB	Output is correct
14	Correct	4 ms	336 KB	Output is correct
15	Correct	6 ms	464 KB	Output is correct
16	Correct	6 ms	464 KB	Output is correct
17	Correct	4 ms	336 KB	Output is correct
18	Correct	6 ms	464 KB	Output is correct
19	Correct	8 ms	464 KB	Output is correct
20	Correct	8 ms	464 KB	Output is correct
21	Correct	6 ms	464 KB	Output is correct
22	Correct	5 ms	464 KB	Output is correct
23	Correct	7 ms	464 KB	Output is correct
24	Correct	4 ms	336 KB	Output is correct
25	Correct	8 ms	384 KB	Output is correct
26	Correct	6 ms	464 KB	Output is correct
27	Correct	6 ms	464 KB	Output is correct
28	Correct	5 ms	464 KB	Output is correct
29	Correct	8 ms	464 KB	Output is correct
30	Correct	6 ms	464 KB	Output is correct
31	Correct	7 ms	464 KB	Output is correct
32	Correct	5 ms	464 KB	Output is correct
33	Correct	6 ms	464 KB	Output is correct
34	Correct	5 ms	464 KB	Output is correct
35	Correct	8 ms	464 KB	Output is correct
36	Correct	5 ms	464 KB	Output is correct
37	Correct	6 ms	464 KB	Output is correct
38	Correct	7 ms	464 KB	Output is correct
39	Correct	6 ms	464 KB	Output is correct
40	Correct	7 ms	464 KB	Output is correct
41	Correct	8 ms	464 KB	Output is correct
42	Correct	6 ms	464 KB	Output is correct
43	Correct	8 ms	464 KB	Output is correct
44	Correct	6 ms	464 KB	Output is correct
45	Correct	7 ms	464 KB	Output is correct
46	Correct	6 ms	464 KB	Output is correct
47	Correct	6 ms	384 KB	Output is correct
48	Correct	7 ms	464 KB	Output is correct
49	Correct	9 ms	464 KB	Output is correct
50	Correct	7 ms	392 KB	Output is correct
51	Correct	5 ms	464 KB	Output is correct
52	Correct	5 ms	464 KB	Output is correct
53	Correct	6 ms	464 KB	Output is correct
54	Correct	6 ms	464 KB	Output is correct
55	Correct	6 ms	464 KB	Output is correct
56	Correct	5 ms	464 KB	Output is correct
57	Correct	8 ms	464 KB	Output is correct
58	Correct	8 ms	388 KB	Output is correct
59	Correct	6 ms	464 KB	Output is correct
60	Correct	6 ms	464 KB	Output is correct
61	Correct	5 ms	464 KB	Output is correct
62	Correct	0 ms	208 KB	Output is correct
63	Correct	0 ms	208 KB	Output is correct
64	Correct	0 ms	208 KB	Output is correct
65	Correct	0 ms	208 KB	Output is correct
66	Correct	0 ms	208 KB	Output is correct
67	Correct	0 ms	208 KB	Output is correct
68	Correct	0 ms	208 KB	Output is correct
69	Correct	0 ms	208 KB	Output is correct
70	Correct	0 ms	208 KB	Output is correct
71	Correct	1 ms	208 KB	Output is correct
72	Correct	0 ms	208 KB	Output is correct
73	Correct	0 ms	208 KB	Output is correct
74	Correct	0 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	0 ms	208 KB	Output is correct
80	Correct	0 ms	208 KB	Output is correct
81	Correct	0 ms	208 KB	Output is correct
82	Correct	0 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	1 ms	208 KB	Output is correct
86	Correct	1 ms	208 KB	Output is correct
87	Correct	1 ms	208 KB	Output is correct
88	Correct	1 ms	208 KB	Output is correct
89	Correct	1 ms	208 KB	Output is correct
90	Correct	1 ms	208 KB	Output is correct
91	Correct	1 ms	208 KB	Output is correct