Submission #1302789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302789		sano	Counting Mushrooms (IOI20_mushrooms)	C++20	80.14 / 100	4 ms	492 KiB

mushrooms

#include "mushrooms.h"
#include <iostream>
#include <cmath>
#include <set>
#define vec vector
#define For(i, n) for(int i = 0; i < n; i++)
using namespace std;

void vypis(vec<int>&x){
	for(auto i : x) cerr << i << ' ';
	cerr << endl;
	return;
}

int count_mushrooms(int n) {
	vec<int> odp(n+1, -1);
	odp[0] = 0;
	vec<int> mo;
	vec<int> p(2, 0);
	mo = {0, 1};
	int x = use_machine(mo);
	if(n == 2){
		if(x == 0) return 2;
		return 1;
	}
	odp[1] = x;
	mo = {1, 2};
	x = use_machine(mo);
	if(x == 1) odp[2] = 1 - odp[1];
	else odp[2] = odp[1];
	int typ = 0;
	int p2 = 0;
	For(i, 3) if(odp[i] == 1) p2++;
	if(p2 > 1) typ = 1;
	mo.clear();
	cerr << "typ " << typ << endl;
	For(i, 3){
		p[odp[i]]++;
		if(odp[i] == typ && mo.size() < 2) mo.push_back(i);
	}
	vypis(mo);
	int som = -1;
	int odm = sqrt(n) + 10;
	for (int i = 3; i < n; i+=2) {
		if(p[0] >= odm || p[1] >= odm){
			som = i;
			break;
		}
		vec<int> nm;
		nm.push_back(mo[0]);
		nm.push_back(i);
		nm.push_back(mo[1]);
		if(i+1 < n) nm.push_back(i+1);
		x = use_machine(nm);
		if((i+1) < n){
			if((x % 2) == 1){
				odp[i+1] = 1 - typ;
				p[odp[i+1]]++;
			}
			else{
				odp[i+1] = typ;
				p[odp[i+1]]++;
			}
		}
		if(x > 1){
			odp[i] = 1 - typ;
			p[odp[i]]++;
		}
		else{
			odp[i] = typ;
			p[odp[i]]++;
		}
	}
	if(som == -1){
		som = n;
	}
	typ = 0;
	mo.clear();
	if(p[1] > p[0]) typ = 1;
	For(i, n){
		if(odp[i] == typ) mo.push_back(i);
	}
	vypis(mo);
	int vel = mo.size();
	cerr << "som " << som << endl;
	for(int i = som; i < n; i+=vel){
		vec<int> nm;
		for(int j = i; j < n && j < (i+vel); j++){
			nm.push_back(mo[j-i]);
			nm.push_back(j);
		}
		x = use_machine(nm);
		int dokopy = (nm.size())/2;
		int druhy = (x%2) + x/2;
		int prvy = dokopy - druhy;
		p[typ] += prvy;
		p[1-typ] += druhy;
	}
	//ak 
	return p[0];
}

• Subtask 1: 80.1418 / 100