Submission #394542

#	Time	Username	Problem	Language	Result	Execution time	Memory
394542		faresbasbs	Counting Mushrooms (IOI20_mushrooms)	C++14	80.14 / 100	11 ms	308 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
const int sq = 146;
vector<int> a,b;
int n;

int ask(vector<int> v){
	return use_machine(v);
}

int base(){
	int ret = 1 , pos = 1;
	if(n%2 == 0){
		pos = 2;
		vector<int> f = {0,1};
		ret += 1-ask(f);
	}
	for(int i = pos ; i < n ; i += 2){
		vector<int> f = {i,0,i+1};
		ret += 2-ask(f);
	}
	return ret;
}

void step1(){
	a = {0};
	vector<int> f = {0,1} , f2 = {0,2};
	if(ask(f) == 0){
		a.push_back(1);
	}else{
		b.push_back(1);
	}
	if(ask(f2) == 0){
		a.push_back(2);
	}else{
		b.push_back(2);
	}
}

void step2(){
	if(a.size() >= 2){
		for(int i = 3 ; i < 2*sq ; i += 2){
			vector<int> f = {a[0],i,a[1],i+1};
			int num = ask(f);
			if(num == 0){
				a.push_back(i),a.push_back(i+1);
			}else if(num == 1){
				a.push_back(i),b.push_back(i+1);
			}else if(num == 2){
				b.push_back(i),a.push_back(i+1);
			}else{
				b.push_back(i),b.push_back(i+1);
			}
		}
	}else{
		for(int i = 3 ; i < 2*sq ; i += 2){
			vector<int> f = {b[0],i,b[1],i+1};
			int num = ask(f);
			if(num == 0){
				b.push_back(i),b.push_back(i+1);
			}else if(num == 1){
				b.push_back(i),a.push_back(i+1);
			}else if(num == 2){
				a.push_back(i),b.push_back(i+1);
			}else{
				a.push_back(i),a.push_back(i+1);
			}
		}
	}
}

int sv1(int pos){
	int num = 0;
	vector<int> f;
	for(int i = 0 , j = pos ; i < sq && j < n ; i += 1 , j += 1){
		f.push_back(a[i]),f.push_back(j),num += 1;
	}
	int val = ask(f);
	return num-(val+1)/2;
}

int sv2(int pos){
	int num = 0;
	vector<int> f;
	for(int i = 0 , j = pos ; i < sq && j < n ; i += 1 , j += 1){
		f.push_back(b[i]),f.push_back(j),num += 1;
	}
	int val = ask(f);
	return (val+1)/2;
}

int step3(){
	int ret = 0;
	if(a.size() > b.size()){
		for(int i = 2*sq+1 ; i < n ; i += sq){
			ret += sv1(i);
		}
	}else{
		for(int i = 2*sq+1 ; i < n ; i += sq){
			ret += sv2(i);
		}
	}
	return ret;
}

int count_mushrooms(int N){
	n = N;
	if(n <= 400){
		return base();
	}
	step1();
	step2();
	return a.size()+step3();
}

• Subtask 1: 80.1418 / 100