Submission #831236

#	Time	Username	Problem	Language	Result	Execution time	Memory
831236		Baytoro	Counting Mushrooms (IOI20_mushrooms)	C++17	90.40 / 100	7 ms	452 KiB

mushrooms

#include "mushrooms.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end();
int count_mushrooms(int n) {
	vector<int> a[2];
	a[0].pb(0);
	int last=1;
	for(int i=1;i<n && max(a[0].size(),a[1].size())<2;i++){
		if(use_machine({0,i})) a[1].pb(i);
		else a[0].pb(i);
		last++;
	}
	for(int i=last;i+1<n && (int)a[0].size()<50 && (int)a[1].size()<50;){
		int x=0;
		if(a[0].size()<2) x=1;
		int cnt=use_machine({a[x][0],i,a[x][1],i+1});
		if(cnt==0) {a[x].pb(i);a[x].pb(i+1);}
		if(cnt==1) {a[x].pb(i);a[x^1].pb(i+1);}
		if(cnt==2) {a[x].pb(i+1);a[x^1].pb(i);}
		if(cnt==3) {a[x^1].pb(i);a[x^1].pb(i+1);}
		i+=2;
		last=i;
	}
	vector<int> A(2);
	A[0]=a[0].size();
	A[1]=a[1].size();
	for(int i=last;i<n;){
		int x=0,s=a[0].size();
		if(s<(int)a[1].size()) x=1,s=a[1].size();
		int l=min(i+s,n);
		vector<int> v;
		for(int j=i;j<l;j++){
			v.pb(a[x][j-i]);
			v.pb(j);
		}
		int cnt=use_machine(v);
		if(cnt%2) A[x^1]++,a[x^1].pb(l-1),cnt--;
		else A[x]++,a[x].pb(l-1);
		A[x^1]+=(cnt+1)/2,A[x]+=(l-i-1-(cnt+1)/2);
		i=l;
	}
	return A[0];
}

• Subtask 1: 90.4 / 100