Submission #1292689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292689		enzy	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	3 ms	424 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int sqt=101;
int solve(int n){
	int resp=0;
	vector<int>a, b;
	a.push_back(0);
	int id=1;
	while(max(a.size(),b.size())<=sqt&&id<n){
		vector<int>aux;
		aux.push_back(0); aux.push_back(id);
		if(use_machine(aux)) b.push_back(id);
		else a.push_back(id);
		id++;
	}
	resp=a.size();
	if(a.size()>=sqt){
		//cout << "A" << endl;
		while(id<n){
			vector<int>aux;
			int qtd=0;
			for(int i=0;i<a.size()-1;i++){
				aux.push_back(a[i]);
				if(id<n){
					aux.push_back(id);
					id++;
					qtd++;
				}
			}
			aux.push_back(a.back());
			resp+=((2*qtd-use_machine(aux))/2);
		}
	}else{
		//cout << "B" << endl;
		while(id<n){
			vector<int>aux;
			int qtd=0;
			for(int i=0;i<b.size()-1;i++){
				aux.push_back(b[i]);
				if(id<n){
					aux.push_back(id);
					id++;
					qtd++;
				}
			}
			aux.push_back(b.back());
			resp+=(use_machine(aux)/2);
		}
	}
	return resp;
}
int count_mushrooms(int n){
	if(n<=2000) return solve(n);
	int resp=0;
	vector<int>a, b;
	a.push_back(0);
	int id=1;
	while(max(a.size(),b.size())<=2&&id<n){
		vector<int>aux;
		aux.push_back(0); aux.push_back(id);
		if(use_machine(aux)) b.push_back(id);
		else a.push_back(id);
		id++;
	}
	if(a.size()>=2){
		while(max(a.size(),b.size())<=sqt&&id<n){
			vector<int>aux;
			aux.push_back(id); id++; 
			aux.push_back(a[0]); 
			aux.push_back(id); id++;
			aux.push_back(a[1]); 
			aux.push_back(id); id++;
			int at1=use_machine(aux);
			if(at1==0){
				a.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
				continue;
			}
			if(at1==4){
				b.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
				continue;
			}
			swap(aux[0],aux[2]);
			int at2=use_machine(aux);
			if(at1==at2&&at1==1){
				a.push_back(aux[0]); a.push_back(aux[2]); b.push_back(aux[4]);
				continue;
			}
			if(at1==at2&&at1==3){
				b.push_back(aux[0]); b.push_back(aux[2]); a.push_back(aux[4]);
				continue;
			}
			if(at1==1){
				b.push_back(aux[0]); a.push_back(aux[2]); b.push_back(aux[4]);
				continue;
			}
			if(at1==3){
				a.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
				continue;
			}
			// ent at1=2, se caiu agr
			if(at2==1){
				b.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
				continue;
			}
			if(at2==3){
				a.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
				continue;
			}
		}
	}else{
		while(max(a.size(),b.size())<=sqt&&id<n){
			vector<int>aux;
			aux.push_back(id); id++; 
			aux.push_back(a[0]); 
			aux.push_back(id); id++;
			aux.push_back(a[1]); 
			aux.push_back(id); id++;
			int at1=use_machine(aux);
			if(at1==0){
				b.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
				continue;
			}
			if(at1==4){
				a.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
				continue;
			}
			swap(aux[0],aux[2]);
			int at2=use_machine(aux);
			if(at1==at2&&at1==1){
				b.push_back(aux[0]); b.push_back(aux[2]); a.push_back(aux[4]);
				continue;
			}
			if(at1==at2&&at1==3){
				a.push_back(aux[0]); a.push_back(aux[2]); b.push_back(aux[4]);
				continue;
			}
			if(at1==1){
				a.push_back(aux[0]); b.push_back(aux[2]); a.push_back(aux[4]);
				continue;
			}
			if(at1==3){
				b.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
				continue;
			}
			// ent at1=2, se caiu agr
			if(at2==1){
				a.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
				continue;
			}
			if(at2==3){
				b.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
				continue;
			}
		}
	}



	// ja ta certo essa parte
	resp=a.size();
	if(a.size()>=sqt){
		//cout << "A" << endl;
		while(id<n){
			vector<int>aux;
			int qtd=0;
			for(int i=0;i<a.size()-1;i++){
				aux.push_back(a[i]);
				if(id<n){
					aux.push_back(id);
					id++;
					qtd++;
				}
			}
			aux.push_back(a.back());
			resp+=((2*qtd-use_machine(aux))/2);
		}
	}else{
		//cout << "B" << endl;
		while(id<n){
			vector<int>aux;
			int qtd=0;
			for(int i=0;i<b.size()-1;i++){
				aux.push_back(b[i]);
				if(id<n){
					aux.push_back(id);
					id++;
					qtd++;
				}
			}
			aux.push_back(b.back());
			resp+=(use_machine(aux)/2);
		}
	}
	return resp;
}

• Subtask 1: 0 / 100