Submission #1239812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239812		SalihSahin	Counting Mushrooms (IOI20_mushrooms)	C++20	56.64 / 100	3 ms	428 KiB

mushrooms

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


int count_mushrooms(int n) {
   if(n <= 226){
      int cnt = 1;
      vector<int> v;
      v.push_back(0);
      for(int j = 1; j < n; j++){
         v.push_back(j);
         int x = use_machine(v);
         if(!x) cnt++;
         v.pop_back();
      }
      return cnt;
   }
   vector<int> type[2];
   type[0].push_back(0);

   vector<int> v;
   v.push_back(0);
   int ind = 0;
   for(int j = 1; j < n; j++){
      v.push_back(j);
      int x = use_machine(v);
      type[x].push_back(j);
      v.pop_back();

      if(max(type[0].size(), type[1].size()) >= 100){
         ind = j+1;
         break;
      }
   }

   int ans = type[0].size();
   while(ind < n){
      vector<int> query;
      if(type[0].size() > type[1].size()){
         int koy = 0;

         for(int i = 0; i < type[0].size()-1; i++){
            query.push_back(type[0][i]);
            if(ind < n){
               query.push_back(ind);
               ind++;
               koy++;
            }
         }
         query.push_back(type[0].back());
         int val = use_machine(query);
         ans += (koy*2 - val) / 2;
      }
      else{
         for(int i = 0; i < type[1].size()-1; i++){
            query.push_back(type[1][i]);
            if(ind < n){
               query.push_back(ind);
               ind++;
            }
         }
         query.push_back(type[1].back());
         int val = use_machine(query);
         ans += (val / 2);
      }
   }

   return ans;
}

• Subtask 1: 56.6416 / 100