Submission #1239807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239807		SalihSahin	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	1 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 K = 200;
   for(int j = 1; j <= K; j++){
      v.push_back(j);
      int x = use_machine(v);
      type[x].push_back(j);
      v.pop_back();
   }

   int ind = K+1, ans = type[0].size();
   while(ind < n){
      vector<int> query;
      if(type[0].size() > type[1].size()){
         for(int i = 0; i < type[0].size()-1; i++){
            query.push_back(type[0][i]);
            if(ind < n){
               query.push_back(ind);
               ind++;
            }
         }
         query.push_back(type[0].back());
         int val = use_machine(query);
         ans += ((type[0].size() - 1) * 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: 0 / 100