Submission #830827

#	Time	Username	Problem	Language	Result	Execution time	Memory
830827		amunduzbaev	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	208 KiB

mushrooms

#include "mushrooms.h"

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
//~ #define int ll

const int N = 20'000;

int count_mushrooms(int n){
	vector<int> p[2];
	p[0].push_back(0);
	
	int B = 2;
	
	int last = 1;
	for(int i=1;i<n && max((int)p[0].size(), (int)p[1].size()) < B;i++){
		last++;
		if(use_machine({0, i})) p[1].push_back(i);
		else p[0].push_back(i);
	}
	
	B = 143;
	for(int i=last;i + 1<n && max((int)p[0].size(), (int)p[1].size()) < B;i++){
		int j = i + 1, id = 0;
		if((int)p[id].size() < 2) id = 1;
		
		int c = use_machine({i, p[id][0], j, p[id][1]});
		if(c == 0) p[id].push_back(i), p[id].push_back(j);
		if(c == 1) p[!id].push_back(i), p[id].push_back(j);
		if(c == 2) p[id].push_back(i), p[!id].push_back(j);
		if(c == 3) p[!id].push_back(i), p[!id].push_back(j);
		
		i = j + 1;
	}
	
	ar<int, 2> cc {};
	cc[0] = p[0].size(), cc[1] = p[1].size();
	
	for(int i=last;i<n;){
		int B = p[0].size(); 
		bool is = 1;
		if((int)p[1].size() > B) is = 0, B = p[1].size();
		
		int j = min(i + B, n);
		
		vector<int> qq;
		for(int k=i;k<j;k++){
			qq.push_back(p[is ^ 1][k - i]);
			qq.push_back(k);
		}
		
		int c = use_machine(qq);
		//~ if(c & 1) cc[is]++, p[is].push_back(j - 1), c--;
		//~ else cc[is ^ 1]++, p[is ^ 1].push_back(j - 1);
		
		cc[is] += (c + 1) / 2, cc[is ^ 1] += (j - i - (c + 1) / 2);
		i = j;
	}
	
	return cc[0];
}

• Subtask 1: 0 / 100