Submission #1186774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186774		owoovo	Counting Mushrooms (IOI20_mushrooms)	C++20	67.06 / 100	3 ms	552 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
#define F first 
#define S second
using namespace std;
int p[20010];
int query(vector<int> vc){
	vector<int> ask=vc;
	for(auto &x:ask){
		x=p[x];
	}
	return use_machine(vc);
}
int count_mushrooms(int n) {
	for(int i=0;i<n;i++)p[i]=i;
	random_shuffle(&p[1],&p[n]);
	vector<int> a={0},b;
	int x=93;
	for(int i=1;i<=min(2*x,n-1);i++){
		int c=query({0,i});
		if(c==0)a.push_back(i);
		else b.push_back(i);
	}
	int ans=a.size(),cnt=min(2*x,n-1)+1;
	while(cnt<n){
		vector<int> q;
		int xd=0,st=cnt;
		if(a.size()>=b.size()){
			for(int i=0;i<a.size();i++){
				if(cnt<n){
					xd++;
					q.push_back(cnt);
					cnt++;
				}
				q.push_back(a[i]);
			}
			int ct=query(q);
			if(ct%2==0){
				a.push_back(st);
			}else{
				b.push_back(st);
			}
			int bs=(ct+1)/2;
			ans+=xd-bs;
		}else{
			for(int i=0;i<b.size();i++){
				if(cnt<n){
					xd++;
					q.push_back(cnt);
					cnt++;
				}
				q.push_back(b[i]);
			}
			int ct=query(q);
			if(ct%2==0){
				b.push_back(st);
			}else{
				a.push_back(st);
			}
			int as=(ct+1)/2;
			ans+=as;
		}
	}
	return ans;
}

• Subtask 1: 67.0623 / 100