Submission #303813

#	Time	Username	Problem	Language	Result	Execution time	Memory
303813		errorgorn	버섯 세기 (IOI20_mushrooms)	C++17	92.62 / 100	10 ms	384 KiB

mushrooms

#include "mushrooms.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

const int LIM=80; //play with this

int n;
vector<int> red;
vector<int> blue;

int count_mushrooms(int N) {
	n=N;
	
	if (n<300){
		int ans=1;
		
		for (int x=1;x<n;x+=2){
			if (x==n-1) ans+=1-use_machine({0,x});
			else ans+=2-use_machine({x,0,x+1});
		}
		
		return ans;
	}
	
	red.push_back(0);
	
	int idx=1;
	while (sz(red)<2 && sz(blue)<2){
		if (use_machine({0,idx})==0) red.push_back(idx++);
		else blue.push_back(idx++);
	}
	
	rep(zzz,0,LIM){
		if (sz(red)>=2){
			int temp=use_machine({idx,red[0],idx+1,red[1]});
			
			if (temp&1) blue.push_back(idx);
			else red.push_back(idx);
			
			if (temp&2) blue.push_back(idx+1);
			else red.push_back(idx+1);
		}
		else{
			int temp=use_machine({idx,blue[0],idx+1,blue[1]});
			
			if (temp&1) red.push_back(idx);
			else blue.push_back(idx);
			
			if (temp&2) red.push_back(idx+1);
			else blue.push_back(idx+1);
		}
		idx+=2;
	}
	
	int ans=sz(red);
	//cout<<sz(red)<<" "<<sz(blue)<<endl;
	
	while (idx<n){ //it is possible to save some queries here by using the last character but do it later (okay done)
		vector<int> temp;
		
		if (sz(red)>sz(blue)){
			rep(x,0,sz(red)){
				temp.push_back(red[x]);
				if (idx+x<n) temp.push_back(idx+x);
			}
			
			int val=use_machine(temp);
			
			ans+=sz(temp)-sz(red)-(val+1)/2;
			idx+=sz(red);
			
			if (val&1) blue.push_back(idx-1);
			else red.push_back(idx-1);
		}
		else{
			rep(x,0,sz(blue)){
				temp.push_back(blue[x]);
				if (idx+x<n) temp.push_back(idx+x);
			}
			
			int val=use_machine(temp);
			
			ans+=(val+1)/2;
			idx+=sz(blue);
			
			if (val&1) red.push_back(idx-1);
			else blue.push_back(idx-1);
		}
	}
	
	return ans;
}

• Subtask 1: 92.623 / 100