oj.uz

답안 #699790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699790 2023-02-18T03:15:33 Z cig32 버섯 세기 (IOI20_mushrooms) C++17
100 / 100
 9 ms 464 KB 
#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

# 결과 실행 시간 메모리 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