Submission #824755

#	Time	Username	Problem	Language	Result	Execution time	Memory
824755		fatemetmhr	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	7 ms	312 KiB

mushrooms

// Be name khoda //

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << "(" << #x << "):" << x << endl;
#define all(x)   x.begin(), x.end();
#define fi       first
#define se       second
#define pb       push_back
#define mp       make_pair

const int ssq   = 141;
const int maxn5 = 1e5 + 10;


vector <int> av, av2;
int cnt[2], ty[maxn5];

int count_mushrooms(int n){

	av = {0, 1};
	int a = use_machine(av);
	ty[0] = 0;
	ty[1] = a;
	if(n == 2){
		if(a)
			return 1;
		return 2;
	}
	av = {0, 2};
	int b = use_machine(av);
	ty[2] = b;
	int x1, x2;
	if(a == 0){
		x1 = 0;
		x2 = 1;
	}
	else if(b == 0){
		x1 = 0;
		x2 = 2;
	}
	else{
		x1 = 1;
		x2 = 2;
	}
	//cout << x1 << ' ' << x2 << endl;

	cnt[0] = 1 + (1 ^ ty[2]) + (1 ^ ty[1]);
	cnt[1] = ty[2] + ty[1];
	int pt = 3;
	while(max(cnt[0], cnt[1]) < ssq && cnt[0] + cnt[1] < n){
		if(pt + 1 == n){
			av = {x1, pt};
			int x = use_machine(av);
			ty[pt] = (ty[x1] ^ x);
			cnt[ty[pt]]++;
			pt++;
			continue;
		}
		av = {x1, pt, x2, pt + 1};
		int x = use_machine(av);
		if(x == 0){
			ty[pt] = ty[pt + 1] = ty[x1];
			cnt[ty[x1]] += 2;
		}
		if(x == 1){
			ty[pt] = ty[x1];
			ty[pt + 1] = ty[x1] ^ 1;
			cnt[ty[x1]]++;
			cnt[ty[x1] ^ 1]++;
		}
		if(x == 2){
			ty[pt] = ty[x1] ^ 1;
			ty[pt + 1] = ty[x1];
			cnt[ty[x1]]++;
			cnt[ty[x1] ^ 1]++;
		}
		if(x == 3){
			ty[pt] = ty[pt + 1] = ty[x1] ^ 1;
			cnt[ty[x1] ^ 1] += 2;
		}
		pt += 2;
	}

	if(cnt[0] + cnt[1] == n)
		return cnt[0];
	int g = 0;
	if(cnt[1] > cnt[0])
		g = 1;
	for(int i = 0; i < pt; i++) if(ty[i] == g)
		av2.pb(i);
	//cout << pt << ' ' << g << ' ' << av2.size() << endl;
	while(pt < n){
		av.clear();
		int ind = 0;
		while(pt < n && ind < av2.size()){
			av.pb(av2[ind++]);
			av.pb(pt++);
		}
		int x = use_machine(av);
		int num = x / 2 + x % 2;
		cnt[g ^ 1] += num;
		cnt[g] += int(av.size()) / 2 - num;
	}
	return cnt[0];
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   while(pt < n && ind < av2.size()){
      |                   ~~~~^~~~~~~~~~~~

• Subtask 1: 80.427 / 100