Submission #1115689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115689		Numberz	Counting Mushrooms (IOI20_mushrooms)	C++14	90.04 / 100	11 ms	952 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int count_mushrooms(int n) {
  vector<int> A_count = {0};
  vector<int> B_count;
  int total = 1;
  //check the small cases
  if (n <= 90) {
    int sum = 1;
    for (int i = 1; i < n; i++) {
      if (use_machine({0, i}) == 0) sum++;
    }
    return sum;
  }

  
  //first we want to reach a decent ammount of a, b fast with x A y A
  //forework
  if (use_machine({0, 1}) == 0) {
    A_count.push_back(1);
    total++;
  } else {
    B_count.push_back(1);
  }
  //same for 2
  if (use_machine({0, 2}) == 0) {
    A_count.push_back(2);
    total++;
  } else {
    B_count.push_back(2);
  }
  //if a == b
  if (A_count.size() > 1) {
    for (int j = 3; j < 88; j+=2) {
      int sum = use_machine({j, 0, j+1, A_count[1]});
      if (sum == 3) {
        B_count.push_back(j);
        B_count.push_back(j+1);
      } else if (sum == 2) {
        A_count.push_back(j);
        B_count.push_back(j+1);
        total++;
      } else if (sum == 1) {
        B_count.push_back(j);
        A_count.push_back(j+1);
        total++;
      } else {
        A_count.push_back(j);
        A_count.push_back(j+1);
        total+=2;
      }
    }
  } else {
    for (int j = 3; j < 88; j+=2) {
      int sum = use_machine({j, B_count[0], j+1, B_count[1]});
      if (sum == 3) {
        A_count.push_back(j);
        A_count.push_back(j+1);
        total+=2;
      } else if (sum == 2) {
        B_count.push_back(j);
        A_count.push_back(j+1);
        total++;
      } else if (sum == 1) {
        A_count.push_back(j);
        B_count.push_back(j+1);
        total++;
      } else {
        B_count.push_back(j);
        B_count.push_back(j+1);
      }
    }
  }
  int i = 89;
  while (i < n) {
    vector<int> temp;
    int d = 0;
    if (A_count.size() >= B_count.size()) {
      while (i < n && d < A_count.size()) {
        temp.push_back(i);
        temp.push_back(A_count[d]);
        i++;
        d++;
      }
      int sum = use_machine(temp);
      if (sum % 2 == 1) {
        B_count.push_back(temp[0]);
      } else {
        A_count.push_back(temp[0]);
      }
      total += (temp.size()/2 - ((sum+1)/2));
      temp.clear();
      //do the same with B
    } else {
      while (i < n && d < B_count.size()) {
        temp.push_back(i);
        temp.push_back(B_count[d]);
        i++;
        d++;
      }
      int sum = use_machine(temp);
      if (sum % 2 == 1) {
        A_count.push_back(temp[0]);
      } else {
        B_count.push_back(temp[0]);
      }
      total += ((sum+1)/2);
      temp.clear();
    }
  }
  
  return total;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:82:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |       while (i < n && d < A_count.size()) {
      |                       ~~^~~~~~~~~~~~~~~~
mushrooms.cpp:98:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |       while (i < n && d < B_count.size()) {
      |                       ~~^~~~~~~~~~~~~~~~

• Subtask 1: 90.0398 / 100