Submission #311059

#	Time	Username	Problem	Language	Result	Execution time	Memory
311059		Lemur95	Counting Mushrooms (IOI20_mushrooms)	C++17	92.24 / 100	11 ms	436 KiB

mushrooms

#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 = 190;

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.2449 / 100