Submission #411432

#	Time	Username	Problem	Language	Result	Execution time	Memory
411432		AKaan37	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	174 ms	428 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

char c[li];
int cev;

inline void boya(int i,int j,int k,char cc){
	char cc1;
	if(cc=='A')cc1='B';
	else cc1='A';
	if(k==0){c[i]=cc;c[j]=cc;}
	if(k==1){c[i]=cc;c[j]=cc1;}
	if(k==2){c[i]=cc1;c[j]=cc;}
	if(k==3){c[i]=cc1;c[j]=cc1;}
}

int count_mushrooms(int n){
	if(n==1)return 1;
	c[0]='A';
	vector<int> v;
	v.pb(0);
	v.pb(1);
	int k=use_machine(v);
	if(k==0)c[1]='A';
	else c[1]='B';
	if(n==2){
		if(c[1]=='A')return 2;
		return 1;
	}
	if(c[1]=='A'){
		for(int i=3;i<n;i+=2){
			v.clear();
			v.pb(0);
			v.pb(i-1);
			v.pb(1);
			v.pb(i);
			k=use_machine(v);
			boya(i-1,i,k,'A');
		}
		if(n%2){
			v.clear();
			v.pb(0);
			v.pb(n-1);
			k=use_machine(v);
			if(k)c[n-1]='B';
			else c[n-1]='A';
		}
		cev=0;
		for(int i=0;i<n;i++){
			if(c[i]=='A')cev++;
		}
		return cev;
	}
	v.clear();
	v.pb(0);
	v.pb(2);
	k=use_machine(v);
	if(k==0)c[2]='A';
	else c[2]='B';
	if(c[2]=='A'){
		for(int i=4;i<n;i+=2){
			v.clear();
			v.pb(0);
			v.pb(i-1);
			v.pb(2);
			v.pb(i);
			k=use_machine(v);
			boya(i-1,i,k,'A');
		}
		if(n%2==0){
			v.clear();
			v.pb(0);
			v.pb(n-1);
			k=use_machine(v);
			if(k)c[n-1]='B';
			else c[n-1]='A';
		}
		cev=0;
		for(int i=0;i<n;i++){
			if(c[i]=='A')cev++;
		}
		return cev;
	}
	for(int i=4;i<n;i+=2){
		v.clear();
		v.pb(1);
		v.pb(i-1);
		v.pb(2);
		v.pb(i);
		k=use_machine(v);
		boya(i-1,i,k,'B');
	}
	if(n%2==0){
		v.clear();
		v.pb(1);
		v.pb(n-1);
		k=use_machine(v);
		if(k)c[n-1]='A';
		else c[n-1]='B';
	}
	cev=0;
	for(int i=0;i<n;i++){
		if(c[i]=='A')cev++;
	}
	return cev;
}

• Subtask 1: 25 / 100