oj.uz

Submission #311082

# Submission time Handle Problem Language Result Execution time Memory
311082 2020-10-09T08:37:00 Z Lemur95 Counting Mushrooms (IOI20_mushrooms) C++17
92.623 / 100
 12 ms 384 KB 
#include <bits/stdc++.h>
#include "mushrooms.h"
#pragma GCC optimize("Ofast")
#define x first
#define y second
#define ld long double
#define ll long long

using namespace std;

const int X = 146;

int q;
vector <bool> s;
vector <vector <int>> p(2);

/*int use_machine(vector <int> v) {
  int ans = 0;
  q++;
  for(int i = 1; i < v.size(); i++)
    ans += (s[v[i]] != s[v[i - 1]]);
  return ans;
}*/

void add(int ind, int i, int &ans) {
  ans += (ind == 0);
  p[ind].push_back(i);
}

int count_mushrooms(int n) {
  vector <int> q;
  p[0].clear();
  p[1].clear();
  int x, ans = 1;
  if(n <= X) {
    for(int i = 1; i < n; i++) {
      q.clear();
      q.push_back(0), q.push_back(i);
      x = use_machine(q);
      ans += (x == 0);
    }
    return ans;
  }
  p[0].push_back(0);
  for(int i = 1; i < 3; i++) {
    q.clear();
    q.push_back(0), q.push_back(i);
    x = use_machine(q);
    add(x, i, ans);
  }
  int a = (p[0].size() >= 2 ? 0 : 1), b = 1 - a;
  for(int i = 3; i <= X; i += 2) {
    q.clear();
    q.push_back(i), q.push_back(p[a][0]), q.push_back(i + 1), q.push_back(p[a][1]);
    x = use_machine(q);
    if(x % 2 == 0)
      add(a, i, ans);
    else
      add(b, i, ans);
    if(x <= 1)
      add(a, i + 1, ans);
    else
      add(b, i + 1, ans);
  }
  int i = X + 1;
  while(i < n) {
    a = (p[0].size() >= p[1].size() ? 0 : 1), b = 1 - a;
    int lim = min(n - i, (int)p[a].size());
    q.clear();
    for(int j = 0; j < lim; j++)
      q.push_back(i + j), q.push_back(p[a][j]);
    x = use_machine(q);
    if(x % 2 == 0)
      p[a].push_back(i);
    else
      p[b].push_back(i);
    i += lim;
    if(a == 0) {
      ans += lim - (x + 1) / 2;
    } else {
      ans += (x + 1) / 2;
    }
  }
  return ans;
}

/*int main() {
  int n, x;
  cin >> n;
  for(int i = 0; i < n; i++)
    cin >> x, s.push_back(x);
  cout << count_mushrooms(n);
  cout << " with " << q << " queries used";
  return 0;
}
*/

Subtask #1
92.623 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 10 ms 256 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 8 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Partially correct 7 ms 288 KB Output is partially correct
12 Correct 7 ms 256 KB Output is correct
13 Correct 6 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Partially correct 12 ms 256 KB Output is partially correct
16 Partially correct 8 ms 288 KB Output is partially correct
17 Correct 5 ms 256 KB Output is correct
18 Correct 6 ms 256 KB Output is correct
19 Partially correct 8 ms 256 KB Output is partially correct
20 Correct 7 ms 256 KB Output is correct
21 Correct 7 ms 256 KB Output is correct
22 Partially correct 7 ms 256 KB Output is partially correct
23 Correct 7 ms 380 KB Output is correct
24 Correct 5 ms 256 KB Output is correct
25 Partially correct 7 ms 256 KB Output is partially correct
26 Partially correct 9 ms 256 KB Output is partially correct
27 Partially correct 9 ms 372 KB Output is partially correct
28 Partially correct 8 ms 380 KB Output is partially correct
29 Partially correct 8 ms 256 KB Output is partially correct
30 Partially correct 7 ms 380 KB Output is partially correct
31 Partially correct 8 ms 256 KB Output is partially correct
32 Partially correct 7 ms 384 KB Output is partially correct
33 Partially correct 8 ms 376 KB Output is partially correct
34 Partially correct 11 ms 256 KB Output is partially correct
35 Partially correct 7 ms 256 KB Output is partially correct
36 Partially correct 9 ms 384 KB Output is partially correct
37 Partially correct 9 ms 256 KB Output is partially correct
38 Partially correct 7 ms 256 KB Output is partially correct
39 Partially correct 7 ms 256 KB Output is partially correct
40 Partially correct 8 ms 256 KB Output is partially correct
41 Partially correct 8 ms 256 KB Output is partially correct
42 Partially correct 9 ms 256 KB Output is partially correct
43 Partially correct 7 ms 256 KB Output is partially correct
44 Partially correct 7 ms 384 KB Output is partially correct
45 Partially correct 8 ms 256 KB Output is partially correct
46 Partially correct 7 ms 256 KB Output is partially correct
47 Partially correct 7 ms 256 KB Output is partially correct
48 Partially correct 7 ms 256 KB Output is partially correct
49 Partially correct 7 ms 256 KB Output is partially correct
50 Partially correct 9 ms 256 KB Output is partially correct
51 Partially correct 7 ms 384 KB Output is partially correct
52 Partially correct 7 ms 256 KB Output is partially correct
53 Partially correct 7 ms 384 KB Output is partially correct
54 Partially correct 8 ms 256 KB Output is partially correct
55 Partially correct 7 ms 384 KB Output is partially correct
56 Partially correct 7 ms 384 KB Output is partially correct
57 Partially correct 7 ms 384 KB Output is partially correct
58 Partially correct 8 ms 256 KB Output is partially correct
59 Partially correct 7 ms 256 KB Output is partially correct
60 Partially correct 7 ms 384 KB Output is partially correct
61 Partially correct 7 ms 256 KB Output is partially correct
62 Correct 0 ms 256 KB Output is correct
63 Correct 0 ms 256 KB Output is correct
64 Correct 0 ms 256 KB Output is correct
65 Correct 0 ms 256 KB Output is correct
66 Correct 1 ms 256 KB Output is correct
67 Correct 1 ms 256 KB Output is correct
68 Correct 1 ms 256 KB Output is correct
69 Correct 1 ms 256 KB Output is correct
70 Correct 1 ms 256 KB Output is correct
71 Correct 1 ms 256 KB Output is correct
72 Correct 1 ms 256 KB Output is correct
73 Correct 1 ms 256 KB Output is correct
74 Correct 1 ms 256 KB Output is correct
75 Correct 0 ms 256 KB Output is correct
76 Correct 0 ms 256 KB Output is correct
77 Correct 1 ms 256 KB Output is correct
78 Correct 1 ms 256 KB Output is correct
79 Correct 0 ms 256 KB Output is correct
80 Correct 0 ms 256 KB Output is correct
81 Correct 1 ms 256 KB Output is correct
82 Correct 0 ms 256 KB Output is correct
83 Correct 0 ms 256 KB Output is correct
84 Correct 1 ms 256 KB Output is correct
85 Correct 1 ms 256 KB Output is correct
86 Correct 0 ms 256 KB Output is correct
87 Correct 1 ms 256 KB Output is correct
88 Correct 0 ms 256 KB Output is correct
89 Correct 0 ms 256 KB Output is correct
90 Correct 1 ms 256 KB Output is correct
91 Correct 0 ms 256 KB Output is correct