Submission #1202553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202553		ansori	Counting Mushrooms (IOI20_mushrooms)	C++20	56.93 / 100	3 ms	428 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 1e9;
int use_machine(std::vector<int> x);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int n){
	ll x = rng();
	return abs(x) % (n + 1);
}
int count_mushrooms(int n) {
	int mn = inf , cnt = 1;
	for(int i = 1;i <= n; ++ i){
		int cnt_query = (i - 1) * 2 + (n - (i * 2 - 1) + i - 1) / i;
		if(cnt_query < mn){
			cnt = i;
			mn = cnt_query;
		}
	}
	//cout << mn << ' ';
	int j = 0 , ans = 0;
	vector<int> psa , psb;
	psa.push_back(0);
	vector<bool> u(n , 0);
	u[0] = 1;
	for(int i = 1;i < n; ++ i){
		int nw = use_machine({0 , i});
		if(nw) psb.push_back(i);
		else psa.push_back(i);
		j = i;
		if(psa.size() >= cnt or psb.size() >= cnt) break;
	}
	ans += psa.size();
	bool pa = true;
	vector<int> ps;
	if(psa.size() >= cnt){
		for(auto to : psa) ps.push_back(to);
	}
	else{
		pa = false;
		for(auto to : psb) ps.push_back(to);
	}
	for(int i = j + 1;i < n; i += cnt){
		vector<int> qu;
		int c = 0;
		for(int z = i;z < min(n , i + cnt); ++ z){
			qu.push_back(z);
			qu.push_back(ps[z - i]);
			c ++;
		}
		int k = use_machine(qu);
		if(! pa) ans += (k + 1) / 2;
		else ans += (c - (k + 1) / 2);
	}
	return ans;
}

• Subtask 1: 56.927 / 100