Submission #303770

#	Time	Username	Problem	Language	Result	Execution time	Memory
303770		kylych03	Counting Mushrooms (IOI20_mushrooms)	C++14	92.62 / 100	16 ms	544 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
//#include "stub.cpp"
using namespace std;
int count_mushrooms(int n) {
	vector<int> m;
	vector <int> a,b;
	srand(time(0));
	for (int i = 0; i < n; i++)
		m.push_back(i);
    random_shuffle(m.begin()+1, m.end());
    int cnt = 0;
    int l=1;
    vector <int> vec1;
    vec1.push_back(0);
    vec1.push_back(m[1]);
    a.push_back(0);
    if(!use_machine(vec1))
    	a.push_back(m[1]);
    else
    	b.push_back(m[1]);
    vec1[1]=m[2];
	if(n>2)
    if(use_machine(vec1)==0)
    	a.push_back(m[2]);
    else
    	b.push_back(m[2]);
    l=3;
    
    while(l < n - 1 && max(a.size(), b.size()) <88 ){
    	vector <int> vec2;
		if(a.size() > 1){
    		vec2.push_back(a[0]);
			vec2.push_back(m[l]);
			vec2.push_back(a[1]);
			vec2.push_back(m[l+1]);
			int res = use_machine(vec2);
			if(res==0){
				a.push_back(m[l]);
				a.push_back(m[l+1]);
			}
			if(res==1){
				a.push_back(m[l]);
				b.push_back(m[l+1]);
			}	
			if(res==2){
				b.push_back(m[l]);
				a.push_back(m[l+1]);
			}
			if(res==3){
				b.push_back(m[l]);
				b.push_back(m[l+1]);
			}
			l=l+2;
		}
		else{
			vec2.push_back(b[0]);
			vec2.push_back(m[l]);
			vec2.push_back(b[1]);
			vec2.push_back(m[l+1]);
			int res = use_machine(vec2);
			if(res==3){
				a.push_back(m[l]);
				a.push_back(m[l+1]);
			}
			if(res==2){
				a.push_back(m[l]);
				b.push_back(m[l+1]);
			}	
			if(res==1){
				b.push_back(m[l]);
				a.push_back(m[l+1]);
			}
			if(res==0){
				b.push_back(m[l]);
				b.push_back(m[l+1]);
			}
			l=l+2;
		}	
    }
    cnt = a.size();
    while(l < n){
    	if(a.size()>= b.size()){
    		vector <int> vec;
    		for(int i = 0 ; i < a.size() && l<n; i++){
    			vec.push_back(a[i]);
    			vec.push_back(m[l]);
    			l++;
			}
			int res = use_machine(vec);
			if(res%2==1)
				b.push_back(vec[vec.size()-1]);
			else
				a.push_back(vec[vec.size()-1]);
			cnt +=(vec.size()/2 - (res+1)/2);
		}
		else{
			vector <int> vec;
    		for(int i = 0 ; i < b.size() && l<n; i++){
    			vec.push_back(b[i]);
    			vec.push_back(m[l]);
    			l++;
			}
			int res = use_machine(vec);
			if(res%2==0)
				b.push_back(vec[vec.size()-1]);
			else
				a.push_back(vec[vec.size()-1]);
			cnt +=((res+1)/2);
		}	
	}
	
	return cnt;
	
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:23:4: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   23 |  if(n>2)
      |    ^
mushrooms.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |       for(int i = 0 ; i < a.size() && l<n; i++){
      |                       ~~^~~~~~~~~~
mushrooms.cpp:99:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |       for(int i = 0 ; i < b.size() && l<n; i++){
      |                       ~~^~~~~~~~~~

• Subtask 1: 92.623 / 100