Submission #1149717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149717		PagodePaiva	버섯 세기 (IOI20_mushrooms)	C++20	0 / 100	2 ms	432 KiB

mushrooms

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

using namespace std;

const int sqr = 123;

int count_mushrooms(int n) {
	vector <int> A, B;
	A.push_back(0);
	for(int i = 1;i < min(n, 2*sqr);i += 3){
		if(i+1 >= min(n, 2*sqr)){
			int t = use_machine({0, i});
			if(t == 1) B.push_back(i);
			else A.push_back(i);
		}
		else if(i+2 >= min(n, 2*sqr)){
			int t = use_machine({0, i});
			if(t == 1) B.push_back(i);
			else A.push_back(i);
			t = use_machine({0,i+1});
			if(t == 1) B.push_back(i+1);
			else A.push_back(i+1);
		}
		else{
			int t = use_machine({0, i, i+1, i+2});
			if(t == 0){
				A.push_back(i);
				A.push_back(i+1);
				A.push_back(i+2);
			}
			else if(t == 1){
				t = use_machine({i+2, 0, i+1, i});
				if(t == 1){
					A.push_back(i);
					A.push_back(i+1);
					B.push_back(i+2);
				}
				else if(t == 3){
					A.push_back(i);
					B.push_back(i+1);
					B.push_back(i+2);
				}
				else{
					B.push_back(i);
					B.push_back(i+1);
					B.push_back(i+2);	
				}
			}
			else if(t == 2){
				t = use_machine({0, i, i+2, i+1});
				if(t == 1){
					A.push_back(i);
					B.push_back(i+1);
					A.push_back(i+2);	
				}
				if(t == 2){
					B.push_back(i);
					A.push_back(i+1);
					A.push_back(i+2);	
				}
				if(t == 3){
					B.push_back(i);
					B.push_back(i+1);
					A.push_back(i+2);	
				}
			}
			else{
				B.push_back(i);
				A.push_back(i+1);
				B.push_back(i+2);
			}
		}
	}
	int st = max(A.back(), (B.empty() ? -1 : B.back()));
	st++;
	if(st == n) return A.size();
	int typ = (A.size() >= (n+sqr-1)/sqr+1 ? 0 : 1);
	int res = A.size();
	for(int i = st;i < min(n, st+sqr);i++){
		vector <int> query;
		int x = i;
		int con = 0;
		while(x < n){
			query.push_back((typ == 0 ? A[(x-st)/(sqr)] : B[(x-st)/(sqr)]));
			query.push_back(x);
			con += 2;
			x += sqr;
		}
		query.push_back((typ == 0 ? A.back() : B.back()));
		res += (typ == 0 ? (con-use_machine(query))/2 : use_machine(query)/2);
	}
	return res;
}

• Subtask 1: 0 / 100