Submission #303669

#	Time	Username	Problem	Language	Result	Execution time	Memory
303669		b00n0rp	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	13 ms	456 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back

int count_mushrooms(int n){
	int cnt = 1;
	vi a,b;
	a.pb(0);
	int LIM = 150; 
	int i;
	for (i = 1; i < LIM; i += 2){
		vi v;
		if(i == n) return cnt;
		if(i == n-1){
			v.pb(0);
			v.pb(i);
			if(use_machine(v) == 0) cnt++;
			return cnt;
		}
		else if(a.size() < 2 and b.size() < 2){
			v.pb(0);
			v.pb(i);
			v.pb(i+1);
			int val = use_machine(v);
			if(val == 0){
				a.pb(i);
				a.pb(i+1);
				cnt += 2;
			}
			else if(val == 2){
				cnt += 1;
				a.pb(i+1);
				b.pb(i);
			}
			else{
				v.clear();
				v.pb(0);
				v.pb(i);
				val = use_machine(v);
				if(val == 1){
					b.pb(i);
					b.pb(i+1);
				}
				else{
					a.pb(i);
					b.pb(i+1);
					cnt ++;
				}
			}
		}
		else{
			if(a.size() >= 2){
				v.pb(0);
				v.pb(i);
				v.pb(a[1]);
				v.pb(i+1);
				int val = use_machine(v);
				if(val == 1 or val == 3){
					b.pb(i+1);
				}
				else{
					a.pb(i+1);
					cnt++;
				}

				if(val == 2 or val == 3){
					b.pb(i);
				}
				else{
					a.pb(i);
					cnt++;
				}
			}
			else{
				v.pb(b[0]);
				v.pb(i);
				v.pb(b[1]);
				v.pb(i+1);
				int val = use_machine(v);
				if(val == 1 or val == 3){
					a.pb(i+1);
					cnt++;
				}
				else{
					b.pb(i+1);
				}

				if(val == 2 or val == 3){
					a.pb(i);
					cnt++;
				}
				else{
					b.pb(i);
				}
			}
		}
	}
	while(i < n){
		vi v;
		if(a.size() > b.size()){
			int j = i;
			int cur = 0;
			while(j < n and cur < (int)a.size()){
				v.pb(a[cur]);
				v.pb(j);
				cur++;
				j++;
			}
			int bruh = use_machine(v);
			int val = ((bruh+1)/2);
			cnt += cur-val;
			if(val == 0){
				FOR(ii,i,j) a.pb(ii);
			}
			else if(val == cur){
				FOR(ii,i,j) b.pb(ii);
			}
			else if(bruh%2){
				b.pb(j-1);
			}
			else{
				a.pb(j-1);
			}
			i = j;
		}
		else{
			int j = i;
			int cur = 0;
			while(j < n and cur < (int)b.size()){
				v.pb(b[cur]);
				v.pb(j);
				cur++;
				j++;
			}
			int bruh = use_machine(v);
			int val = ((bruh+1)/2); 
			cnt += val;
			if(val == 0){
				FOR(ii,i,j) b.pb(ii);
			}
			else if(val == cur){
				FOR(ii,i,j) a.pb(ii);
			}
			else if(bruh%2){
				a.pb(j-1);
			}
			else{
				b.pb(j-1);
			}
			i = j;
		}
	}
	return cnt;
}

• Subtask 1: 92.623 / 100