Submission #1230637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230637		clemmy14	Counting Mushrooms (IOI20_mushrooms)	C++20	53.68 / 100	3 ms	432 KiB

mushrooms

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

// int firstTrue(int lo, int hi) {
// 	hi++;
// 	while(lo < hi) {
// 		int mid = lo+(hi-lo)/2;
// 		if(lo == mid) return lo+1;
// 		vector<int> cur;
// 		for(int i=lo; i<=mid; i++) cur.push_back(i);
// 		int nbAdj=use_machine(cur);
// 		if(nbAdj >= 1) hi=mid;
// 		else if(nbAdj == hi-lo) return lo+1;
// 		else lo=mid;
// 	}
// 	return lo+1;
// }

int cal(vector<int>&v, int st, int n) {
	set<int> s;
	for(auto x : v) s.insert(x);
	int ans=v.size();

	// for(auto x : a) cout << x << ' ';
	// cout << endl;

	for(int i=st; i<n; i++) {
		vector<int> cur;
		int idx=0;
		while(idx < v.size() && i < n) {
			if(s.count(i)) {
				i++; continue;
			}
			cur.push_back(v[idx]);
			cur.push_back(i);
			idx++; i++;
		}
		if(cur.size() == 1) continue;
		int val=use_machine(cur);
		if(val%2 == 0) ans++;
		// for(auto x : cur) cout << x << ' ';
		// cout << endl;
		ans+=(cur.size()-1-val)/2;
		i--;
	}
	return ans;
}

int count_mushrooms(int n) {
	vector<int> a={0}, b;
	// int lo=0;
	// bool aa=true;
	// while(lo != n) {
	// 	int lolo=firstTrue(lo, n-1);
	// 	if(aa) for(int i=lo; i<lolo; i++) a.push_back(i);
	// 	else for(int i=lo; i<lolo; i++) b.push_back(i);
	// 	lo=lolo;
	// 	aa=!aa;
	// 	if(a.size() > sqrt(n) || b.size() > sqrt(n)) break;
	// }
	int lo=2*sqrt(n);
	for(int i=1; i<lo; i++) {
		if(use_machine({0, i}) == 1) b.push_back(i);
		else a.push_back(i);
		if(a.size() >= sqrt(n) || b.size() > sqrt(n)) {
			lo=i+1; break;
		}
	}
	int ans=0;
	if(a.size() >= sqrt(n)) ans = cal(a, lo, n);
	else ans=n-cal(b, lo, n);
	return ans;
}

• Subtask 1: 53.6817 / 100