Submission #1359504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359504		FZ_Laabidi	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	0 ms	348 KiB

mushrooms

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

int count_mushrooms(int n) {
	set<int> v;
	int q = 2*sqrt(n);
	set<int> a;
	a.insert(0);
	if(n<=226){
		int a = 0;
		for(int i=1; i<n; i++){
			a+=use_machine({0, i});
		}
		return a;
	}
	int first = use_machine({1, 0, 2});
	int touse, tovis =0;
	bool flag= true;
	if(first ==0){
		touse = 1;
		a.insert(1);
		a.insert(2);
	}
	else if(first==2) {
		touse=1; tovis = 2;
		v.insert(1);
		v.insert(2);
		flag = false;
	}
	else{
		first = use_machine({1, 0});
		if(first==1)touse = 2;
		else touse = 1;
		a.insert(1);
	}
	for(int i=3; i<q-1; i+=2){
		int x = use_machine({touse, i, tovis, i+1});
		if(flag){
			if(x%2==0){
				v.insert(i+1);
				if(x!=0)v.insert(i);
			}
			else{
				v.insert(i);
			}
		}
		else{
			if(x%2==0){
				a.insert(i+1);
				if(x!=0)a.insert(i);
			}
			else{
				a.insert(i);
			}
		}
		
	}
	int vv = v.size(), aa = a.size();
	 flag = (vv<=aa);
	int fac = max(vv, aa);
	for(int i=q+1; i<n; i+=fac){
		vector<int> mm;
		if(flag){
		    int vo = 0;
			for(auto it: a){
				mm.push_back(it);
				mm.push_back(vo);
				vo++;
			}
			int vi = use_machine(mm);
			aa+=(fac-(vi+1)/2);
		}
		else{
			int vo = 0;
			for(auto it: v){
				mm.push_back(it);
				mm.push_back(vo);
				vo++;
			}
			int vi = use_machine(mm);
			aa+=(vi+1)/2;

		}
		
		return aa;
	}
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
   89 | }
      | ^

• Subtask 1: 0 / 100