제출 #800297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800297		lukameladze	버섯 세기 (IOI20_mushrooms)	C++17	75.08 / 100	8 ms	396 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, 200);
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:56:22: 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:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |  int xr = res[x] ^ 1;
      |                ^
mushrooms.cpp:35:10: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |   to_ask = {i, x, i + 1, y};
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 75.0831 / 100