Submission #1231494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231494		jellybean	Counting Mushrooms (IOI20_mushrooms)	C++20	56.78 / 100	3 ms	428 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define fi first
#define se second
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define dl(x) cout<<#x<<" is "<<endl; for(auto i:x) cout<<i<<" "; cout<<endl;

vector<int>a;
vector<int>b;
int res;

void query(vector<int> &v, vector<int>&x, int n){
	vector<int>m;
	for(int i=0; i<n; i++) {
		m.pb(v[i]);
		m.pb(x[i]);
	}
	m.pb(v[n]);
	res += n-use_machine(m)/2;
}

int count_mushrooms(int n) {
	
	if(n<205){
		int ans = 1;
		for(int i=1; i<n; i++){
			if(!use_machine({0,i})) ans++;
		}
		return ans;
	}
	
	a.pb(0);
	
	for(int i=1; i<n; i++){
		if(!use_machine({0,i})) a.pb(i);
		else b.pb(i);
		if(a.size() == 101 or b.size() == 101) break;
	}
	
	bool f=0;
	if(b.size() == 101) swap(a,b), f=1;
	
	int st=a.size() + b.size();
	
	vector<int>test;
	for(int i=st; i<n; i++){
		test.pb(i);
		if(test.size()==100){
			query(a,test,100);
			test.clear();
		}
	}
	query(a,test,test.size());
	
	res += a.size();
	if(f) res=n-res;
	
	return res;
}

• Subtask 1: 56.7839 / 100