Submission #800299

#	Time	Username	Problem	Language	Result	Execution time	Memory
800299		lukameladze	Counting Mushrooms (IOI20_mushrooms)	C++17	79.58 / 100	8 ms	392 KiB

mushrooms

    #include "mushrooms.h"
    #include <bits/stdc++.h>
    using namespace std;
    #define f first
    #define s second
    #define pii pair <int, int>
    #define pb push_back
    const int MX = 3e5 + 5;
    int count_mushrooms(int n) {
    	vector <int> to_ask; vector <int> res(n, 0);
    	res[0] = 1; // res[i] == (1 _ 'A')        res[i] == (0 _ 'B')
    	
    	to_ask = {0, 1};
    	int c = use_machine(to_ask);
    	res[1] = (c ? 0 : 1); 
    	if (n == 2) {
    		return res[0] + res[1];
    	}
    	to_ask = {0, 2};
    	c = use_machine(to_ask);
    	res[2] = (c ? 0 : 1);
    	int x, y;
    	if (res[0] == res[1]) x = 0, y = 1; 
    	else if (res[0] == res[2]) x = 0, y = 2;
    	else if (res[1] == res[2]) x = 1, y = 2;
    	int ans = (res[0] + res[1] + res[2]);
    	int xr = res[x] ^ 1;
    	int B = min(n, 300);
    	for (int i = 3; i < B; i+=2) {
    		if (i == B - 1) {
    			to_ask = {0, i}; int c = use_machine(to_ask); res[i] = (c ? 0 : 1);
    			ans += res[i]; 
    			continue;
    		}
    		to_ask = {i, x, i + 1, y};
    		int c = use_machine(to_ask);
    		if (c == 0) { res[i] = res[i + 1] = 1; }
    		else if (c == 1) { res[i] = 0; res[i + 1] = 1; }
    		else if (c == 2) { res[i] = 1; res[i + 1] = 0; }
    		else if (c == 3) { res[i] = res[i + 1] = 0;  }
    		res[i] ^= xr; res[i + 1] ^= xr;
    		ans += (res[i] + res[i + 1]); 
    	}
    	vector <int> vec[2];
    	for (int i = 0; i < B; i++) {
    		vec[res[i]].pb(i);
    	}
    	// cout<<"sizes "<<vec[0].size()<<" "<<vec[1].size()<<"\n";
    	vector <int> my_vec;
    	if (vec[0].size() > vec[1].size()) xr = 1, my_vec = vec[0];
    	else xr = 0, my_vec = vec[1];
    	vector <int> cur_vec;
    	for (int i = B; i < n; i++) {
    		cur_vec.pb(i);
    		//cout<<i<<" --- > "<<cur_vec.size()<<"\n";
    		if (cur_vec.size() == (int)my_vec.size() - 1 || i == n - 1) {
    			vector <int> to_ask;
    			int all = (int)cur_vec.size();
    			for (int i = 0; i < (int)cur_vec.size(); i++) {
    				 to_ask.pb(my_vec[i]); to_ask.pb(cur_vec[i]);
    			}
    			to_ask.pb(my_vec.back());
    			//cout<<i<<" "<<cur_vec.size()<<" "<<to_ask.size()<<" --- > ";
    			// for (int id : to_ask) cout<<id<<" ";
    			//cout<<"\n";
    			int c = use_machine(to_ask);
    			
    			if (xr == 0) ans += (2 * all - c) / 2;
    			else ans += c / 2;
    			cur_vec.clear();
    		}
    	}
    	return ans;
    }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:56:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |       if (cur_vec.size() == (int)my_vec.size() - 1 || i == n - 1) {
      |           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:27:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |      int xr = res[x] ^ 1;
      |                    ^
mushrooms.cpp:35:14: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |       to_ask = {i, x, i + 1, y};
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 79.5775 / 100