Submission #1231769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231769		jellybean	Counting Mushrooms (IOI20_mushrooms)	C++20	92.24 / 100	3 ms	456 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;

const int N = 70;
vector<int>a;
vector<int>b;
int ans;

void get2(int &x, int &y, int &type){
	if(use_machine({0,1})){
		b.pb(1);
		if(use_machine({0,2})){
			b.pb(2);
			x=1,y=2,type=1;
		} else {
			a.pb(2);
			x=0,y=2,type=0;
		}
	} else {
		a.pb(1);
		x=0, y=1, type=0;
	}
}

void get100(int x, int y, vector<int> &v, vector<int> &w, int n){
	int st = v.size()+w.size();
	for(int i=st; i<n-1; i+=2){
		int res = use_machine({x,i,y,i+1});
		if(res == 0) v.pb(i), v.pb(i+1);
		else if(res == 1) v.pb(i), w.pb(i+1);
		else if(res == 2) v.pb(i+1), w.pb(i);
		else w.pb(i), w.pb(i+1);
		
		if(v.size() >= N or w.size() >= N) break;
	}
}

void query(vector<int>&x){
	vector<int> &ref = (a.size() > b.size())? a : b;
	vector<int> &notref = (a.size() > b.size())? b : a;
	
	int n = x.size();
	vector<int>m;
	for(int i=0; i<n; i++) {
		m.pb(ref[i]);
		m.pb(x[i]);
	}
	
	int res = use_machine(m);
	if(a.size() > b.size()) ans += n-(res+1)/2;
	else ans += (res+1)/2;
	
	if(res%2) notref.pb(x.back());
	else ref.pb(x.back());
	x.clear();
}

int count_mushrooms(int n) {
	
	if(n==2){
		if(use_machine({0,1})) return 1;
		else return 2;
	}
	
	a.pb(0);
	
	int x,y,type;
	get2(x,y,type);
	if(type == 0) get100(x,y,a,b,n);
	else get100(x,y,b,a,n);
	
	ans = a.size();
	
	int st=a.size() + b.size();
	vector<int>test;
	for(int i=st; i<n; i++){
		test.pb(i);
		if(test.size() == max(a.size(),b.size())) query(test);
	}
	
	if(test.size()) query(test);
	
	return ans;
}

• Subtask 1: 92.2449 / 100