Submission #1052349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052349		mychecksedad	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	5 ms	712 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second


int count_mushrooms(int n) {
	// int mn = 1000000, sz;
	// for(int k = 2; k <= 500; ++k){
	// 	int q = k;
	// 	int kk = k;
	// 	int rem = 20000 - k;
	// 	for(; rem > 0; ){
	// 		rem -= k;
	// 		rem -= k;
	// 		k++;
	// 		q+=2;
	// 	}
	// 	if(mn>q) sz=kk;
	// 	k = kk;
	// 	mn=min(mn,q);
	// }
	// cout << mn << ' ' << sz;
	vector<int> A, B;
	A.pb(0);

	int last = 1, add = 0;
	int q = use_machine({0, 1});
	if(q == 0){
		A.pb(1);
		last = 2;
	}else{
		B.pb(1);
		last =2 ;
		if(n == 2) return 1;
		int q = use_machine({0, 2});
		if(q == 1) B.pb(2);
		else A.pb(2);
		last = 3;
	}
	for(int i = 0; i < 84 && last + 1 < n; ++i){
		if(A.size()>1){
			int x = use_machine({A[0], last, A[1], last + 1});
			if(x % 2 == 0) A.pb(last + 1);
			else B.pb(last + 1);

			if(x > 1) B.pb(last);
			else A.pb(last);
			last += 2;
		}else{
			int x = use_machine({B[0], last, B[1], last + 1});
			if(x % 2 == 0) B.pb(last + 1);
			else A.pb(last + 1);

			if(x > 1) A.pb(last);
			else B.pb(last);
			last += 2;
		}
	}
	while(last < n){
		if(A.size() > B.size()){
			vector<int> q;
			int s = A.size();
			for(int j = last; j < min(n, last + s); ++j){
				q.pb(j);
				q.pb(A[j - last]);
			}
			last = min(n, last + s);
			int f = use_machine(q);
			s = q.size()/2 - 1;
			add += s - f/2;
			if(f%2==0) A.pb(q[0]);
			else B.pb(q[0]);
		}else{
			vector<int> q;
			int s = B.size();
			for(int j = last; j < min(n, last + s); ++j){
				q.pb(j);
				q.pb(B[j - last]);
			}
			int f = use_machine(q);
			add += f/2;
			if(f%2==1) A.pb(q[0]);
			else B.pb(q[0]);

			last = min(n, last + s);
		}
	}


	return int(A.size()) + add;
}

• Subtask 1: 92.623 / 100