Submission #1202579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202579		ansori	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	3 ms	460 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) ;
int count_mushrooms(int n) {
	int ans = 1;
	vector<int> psa , psb;
	psa.push_back(0);
	int j = 1;
	while(j < n){
		vector<int> ps;
		bool pa = true;
		int msz = 0;
		if(psa.size() >= psb.size()){
			msz = psa.size();
			for(auto to : psa) ps.push_back(to);
		}
		else{
			pa = false;
			msz = psb.size();
			for(auto to : psb) ps.push_back(to);
		}
		int lps = j , c = 0;
		vector<int> qu;
		for(int i = j;i < min(n , j + msz); ++ i){
			lps = i;
			qu.push_back(ps[i - j]);
			qu.push_back(i);
			c ++;
		}
		j = min(n , j + msz);
		//cout << c << ' ' << pa << '\n';
		int k = use_machine(qu);
		if(! pa){
			ans += (k + 1) / 2;
			if(k % 2 == 0) psb.push_back(lps);
			else psa.push_back(lps);
		}
		else{
			ans += (c - (k + 1) / 2);
			if(k % 2 == 1) psb.push_back(lps);
			else psa.push_back(lps);			
		}
	}
	return ans;
}

• Subtask 1: 80.7143 / 100