제출 #1230626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230626		clemmy14	버섯 세기 (IOI20_mushrooms)	C++20	0 / 100	0 ms	420 KiB

mushrooms

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

int firstTrue(int lo, int hi) {
	hi++;
	while(lo < hi) {
		int mid = lo+(hi-lo)/2;
		if(lo == mid) return lo+1;
		vector<int> cur;
		for(int i=lo; i<=mid; i++) cur.push_back(i);
		int nbAdj=use_machine(cur);
		if(nbAdj >= 1) hi=mid;
		else if(nbAdj == hi-lo) return lo+1;
		else lo=mid;
	}
	return lo+1;
}


int count_mushrooms(int n) {
	vector<int> a, b;
	int lo=0;
	bool aa=true;
	while(lo != n) {
		int lolo=firstTrue(lo, n-1);
		if(aa) for(int i=lo; i<lolo; i++) a.push_back(i);
		else for(int i=lo; i<lolo; i++) b.push_back(i);
		lo=lolo;
		aa=!aa;
		if(a.size() > sqrt(n) || b.size() > sqrt(n)) break;
	}
	int ans=0;
	if(a.size() > sqrt(n)) {
		set<int> s;
		for(auto x : a) s.insert(x);
		ans=a.size();

		for(int i=lo; i<n; i+=a.size()-1) {
			vector<int> cur={a[0]};
			int ii=i, idx=1;
			while(idx < a.size() && ii < n) {
				if(s.count(ii)) {
					ii++; continue;
				}
				cur.push_back(ii);
				cur.push_back(a[idx]);
				idx++; ii++;
			}
			if(cur.size() == 1) continue;
			ans+=(cur.size()-use_machine(cur))/2;
		}
	} else {
		set<int> s;
		for(auto x : b) s.insert(x);
		ans=b.size();
	
		for(int i=lo; i<n; i+=a.size()-1) {
			vector<int> cur={b[0]};
			int ii=i, idx=1;
			while(idx < b.size() && ii < n) {
				if(s.count(ii)) {
					ii++; continue;
				}
				cur.push_back(ii);
				cur.push_back(b[idx]);
				idx++; ii++;
			}
			if(cur.size() == 1) continue;
			ans+=(cur.size()-use_machine(cur))/2;
		}
		ans=n-ans;
	}
	return ans;
}

• Subtask 1: 0 / 100