Submission #396242

#	Time	Username	Problem	Language	Result	Execution time	Memory
396242		faresbasbs	Counting Mushrooms (IOI20_mushrooms)	C++14	91.87 / 100	10 ms	332 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
const int sq = 100;
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 < a.size() && j < n ; i += 1 , j += 1){
		f.push_back(a[i]),f.push_back(j),num += 1;
	}
	num -= 1;
	int val = ask(f);
	if(val%2 == 0){
		a.push_back(f.back());
	}else{
		b.push_back(f.back());
	}
	return num-val/2;
}
 
int sv2(int pos){
	int num = 0;
	vector<int> f;
	for(int i = 0 , j = pos ; i < b.size() && j < n ; i += 1 , j += 1){
		f.push_back(b[i]),f.push_back(j),num += 1;
	}
	num -= 1;
	int val = ask(f);
	if(val%2 == 0){
		b.push_back(f.back());
	}else{
		a.push_back(f.back());
	}
	return val/2;
}
 
int step3(){
	int ret = 0 , pos = 2*sq+1;
	while(pos < n){
		if(a.size() > b.size()){
			int nxt = pos+a.size();
			ret += sv1(pos);
			pos = nxt;
		}else{
			int nxt = pos+b.size();
			ret += sv2(pos);
			pos = nxt;
		}
	}
	return ret;
}
 
int count_mushrooms(int N){
	n = N;
	if(n <= 400){
		return base();
	}
	step1();
	step2();
	return step3()+a.size();
}

Compilation message (stderr)

mushrooms.cpp: In function 'int sv1(int)':
mushrooms.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0 , j = pos ; i < a.size() && j < n ; i += 1 , j += 1){
      |                            ~~^~~~~~~~~~
mushrooms.cpp: In function 'int sv2(int)':
mushrooms.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0 , j = pos ; i < b.size() && j < n ; i += 1 , j += 1){
      |                            ~~^~~~~~~~~~

• Subtask 1: 91.8699 / 100