Submission #1228183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228183		Nonoze	Counting Mushrooms (IOI20_mushrooms)	C++20	56.36 / 100	3 ms	432 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)x.size()
using namespace std;

int n;
vector<int> A(1, 0), B;
const int LIMIT=95;

int calcone(int &i) {
	// cout << "OK" << endl;
	auto val=2-use_machine({i, A[0], i+1});
	if (val==2) A.pb(i), A.pb(i+1);
	else if (val==0) B.pb(i), B.pb(i+1);
	else {
		if (!use_machine({A[0], i})) A.pb(i), B.pb(i+1);
		else A.pb(i+1), B.pb(i);
	}
	i+=2;
	return val;
}

int calcA(int &i) {
	int l=i, r=min(n-1, i+sz(A)-2);
	vector<int> m;
	for (auto &u: A) {
		if (i>=n) break;
		m.pb(u), m.pb(i++);
	}
	m.pop_back(), i-=2; while (i>=n) m.pop_back(), m.pop_back(), i--;
	i++;
	auto val=sz(m)/2 - use_machine(m)/2;
	int cnt=0;
	for (; l<r && cnt<val&&max(sz(A), sz(B))<LIMIT; l++) {
		if (!use_machine({A[0], l})) A.pb(l), cnt++;
		else B.pb(l);
	}
	if (max(sz(A), sz(B))<LIMIT) {
		if (cnt<val) A.pb(l);
		else B.pb(l);
	}
	return val;
}

int calcB(int &i) {
	int l=i, r=min(n-1, i+sz(B)-2);
	vector<int> m;
	for (auto &u: B) {
		m.pb(u), m.pb(i++);
	}
	m.pop_back(), i-=2; while (i>=n) m.pop_back(), m.pop_back(), i--;
	i++;
	auto val=use_machine(m)/2;
	int cnt=0;
	for (; l<r && cnt<val&&max(sz(A), sz(B))<LIMIT; l++) {
		if (!use_machine({A[0], l})) A.pb(l), cnt++;
		else B.pb(l);
	}
	if (max(sz(A), sz(B))<LIMIT) {
		if (cnt<val) A.pb(l);
		else B.pb(l);
	}
	return val;
}


int count_mushrooms(int _n) { n=_n;
	int ans=1;
	for (int i=1; i<n;) {
		// cout << i << ' ';
		if (i==n-1) {
			ans+=1-use_machine({0, i});
			i++;
		} else {
			if (sz(A)>sz(B) || sz(B)<3) {
				if (sz(A)<=2) ans+=calcone(i);
				else ans+=calcA(i);
			} else {
				ans+=calcB(i);
			}
		}
		// cout << i-1 << ' ' << ans << endl;
	}
	// assert(n<1000 || max(sz(A), sz(B))>=30);
	return ans;
}

• Subtask 1: 56.3591 / 100