Submission #1239830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239830		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 = 1;

   int X = 100;
   while(ind < n){
      v.push_back(ind);
      int x = use_machine(v);
      type[x].push_back(ind);
      v.pop_back();
      ind++;

      if(max(type[0].size(), type[1].size()) >= X){
         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);

         int cnt0 = (koy * 2 - val) / 2;
         int cnt1 = koy - cnt0;
         ans += cnt0;

         int valnow = (n - ind + (type[0].size() - 1)) / (type[0].size());
         int valnxt = koy + (n - ind + (type[0].size() + cnt0 - 1)) / (type[0].size() + cnt0);
         if(type[1].size() + cnt1 > X) valnxt = min(valnxt, koy + (int)((n - ind + (type[1].size() + cnt1 - 1)) / type[1].size()) + cnt1);

         if(valnxt < valnow){
            vector<int> v;
            v.push_back(0);
            for(int j = ind - koy; j < ind; j++){
               if(j < 0) abort();
               v.push_back(j);
               int x = use_machine(v);
               type[x].push_back(j);
               v.pop_back();
            }
         }

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

         int valnow = (n - ind + (type[1].size() - 1)) / (type[1].size());
         int valnxt = koy + (n - ind + (type[1].size() + cnt1 - 1)) / (type[1].size() + cnt1);
         if(type[0].size() + cnt0 > X) valnxt = min(valnxt, koy + (int)((n - ind + (type[0].size() + cnt0 - 1)) / type[0].size()) + cnt0);

         if(valnxt < valnow){
            vector<int> v;
            v.push_back(0);
            for(int j = ind - koy; j < ind; j++){
               if(j < 0) abort();
               v.push_back(j);
               int x = use_machine(v);
               type[x].push_back(j);
               v.pop_back();
            }
         }

      }
   }

   return ans;
}

• Subtask 1: 56.6416 / 100