Submission #1149948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149948		PagodePaiva	버섯 세기 (IOI20_mushrooms)	C++20	77.13 / 100	5 ms	744 KiB

mushrooms

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

using namespace std;

const int N = 20010;
const int sqr = 141;
int mark[N];

int count_mushrooms(int n) {
	vector <int> A, B;
	A.push_back(0);
	vector <int> aux;
	for(int i = 0;i < n;i++){
		aux.push_back(i);
	}
	int tt = use_machine(aux);
	if(tt == 1){
		int x = use_machine({0, 1});
		if(x == 1){
			return 1;
		}
		A.push_back(1);
	}
	else if(tt == 0){
		return n;
	}
	else{
		int x =  use_machine({0, 1});
		if(x == 0){
			A.push_back(1);
		}
		else{
			int l = 2, r = n-1;
			int ans = 0;
			int start = 1;
			while(l <= r){
				if(l == r){
					A.push_back(l);
					ans = l;
					break;
				}
				int mid = (l+r)/2;
				aux.clear();
				for(int i = start;i <= mid;i++){
					aux.push_back(i);
				}
				tt = use_machine(aux);
				if(tt%2 == 0){
					B.push_back(mid);
					if(tt < 1){
						l = mid+1;
						start = mid;
					}
					else if(tt > 1){
						r = mid-1;
					}
				}
				else{
					A.push_back(mid);
					break;
				}
			}
		}
	}
	unique(A.begin(), A.end());
	unique(B.begin(), B.end());
	for(auto x :A){
		mark[x] = 1;
	}
	for(auto x : B){
		mark[x] = 1;
	}
	vector <int> valores;
	for(int i = 0;i < n;i++){
		if(!mark[i]) valores.push_back(i);
	}
	int cnt = 0;
	for(int i = 0;i < min((int)valores.size(), 2*(((int)valores.size()+sqr-1)/sqr+1));i += 2){
		if(i+1 == min((int)valores.size(), 2*(((int)valores.size()+sqr-1)/sqr+1))){
			int t = use_machine({0, valores[i]});
			if(t == 1) B.push_back(valores[i]);
			else A.push_back(valores[i]);
			cnt++;
		}
		else{
			//cout << valores[i] << ' ' << A[1] << ' ' << valores[i+1] << endl;
			int t = use_machine({0, valores[i], A[1], valores[i+1]});
			if(t == 0){
				A.push_back(valores[i]);
				A.push_back(valores[i+1]);
			}
			else if(t == 1){
				A.push_back(valores[i]);
				B.push_back(valores[i+1]);
			}
			else if(t == 2){
				B.push_back(valores[i]);
				A.push_back(valores[i+1]);
			}
			else{
				B.push_back(valores[i]);
				B.push_back(valores[i+1]);
			}
			cnt += 2;
		}
	}
	if(cnt == (int)valores.size()) return A.size();
	int typ = (A.size() >= B.size() ? 0 : 1);
	int res = A.size();
	for(int i = cnt;i < min((int)valores.size(), cnt+sqr);i++){
		vector <int> query;
		int x = i;
		int con = 0;
		while(x < (int)valores.size()){
			query.push_back((typ == 0 ? A[(x-cnt)/(sqr)] : B[(x-cnt)/(sqr)]));
			query.push_back(valores[x]);
			con += 2;
			x += sqr;
		}
		query.push_back((typ == 0 ? A.back() : B.back()));
		/*for(auto x : query){
			cout << x << ' ';
		}*/
		//cout << endl;
		res += (typ == 0 ? (con-use_machine(query))/2 : use_machine(query)/2);
	}
	return res;
}

• Subtask 1: 77.1331 / 100