Submission #1239952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239952		SalihSahin	Counting Mushrooms (IOI20_mushrooms)	C++20	84.64 / 100	3 ms	436 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()) >= 2){
         ind = j+1;
         break;
      }
   }

   int X = 125;

   if(type[0].size() >= 2){
      while(ind < n){
         if(max(type[0].size(), type[1].size()) >= X) break;
         vector<int> v = {0, ind, type[0][1], ind + 1};
         int x = use_machine(v);
         type[((x&2) > 0)].push_back(ind);
         type[x&1].push_back(ind+1);
         ind += 2;
      }
   }
   else{
      while(ind < n){
         if(max(type[0].size(), type[1].size()) >= X) break;
         vector<int> v = {type[1][0], ind, type[1][1], ind + 1};
         int x = use_machine(v);
         type[!((x&2) > 0)].push_back(ind);
         type[!(x&1)].push_back(ind+1);
         ind += 2;
      }
   }

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

   return ans;
}

• Subtask 1: 84.6442 / 100