oj.uz

답안 #1079991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079991 2024-08-29T05:38:46 Z UmairAhmadMirza 버섯 세기 (IOI20_mushrooms) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
using namespace std;

int const N=20005;
int const H=141;

int use_machine(vector<int> x);

int solve(int n){
	vector<int> A,B;
	A.push_back(0);
	vector<int> q;
	q.push_back(0);
	for(int i=1;i<n;i++){
		q.push_back(i);
		if(use_machine(q))
			B.push_back(i);
		else
			A.push_back(i);
		q.pop_back();
		if(A.size()>=100 || B.size()>=100)
			break;
	}
	bool bl=0;
	if(A.size()<B.size()){
		swap(A,B);
		bl=1;
	}
	int cntA=A.size(),cntB=B.size();
	for(int i=(A.size()+B.size());i<n;i+=H){
		vector<int> q;
		for(int j=i;j<min(i+H,n);j++){
			q.push_back(A[j-i]);
			q.push_back(j);
		}
		int v=use_machine(q)+1;
		cntB+=v/2;
	}
	cntA=n-cntB;
	if(bl)
		swap(cntB,cntA);
	return cntA;
}

int count_mushrooms(int n){
	if(n<=282)
		return solve(n);
	vector<int> A,B;
	A.push_back(0);
	vector<int> q;
	q.push_back(0);
	for(int i=1;i<n;i++){
		q.push_back(i);
		if(use_machine(q))
			B.push_back(i);
		else
			A.push_back(i);
		q.pop_back();
		if(A.size()>=2 || B.size()>=2)
			break;
	}
	bool bl=0;
	if(A.size()<B.size()){
		swap(A,B);
		bl=1;
	}
	q.clear();
	int dn=A.size()+B.size();
	for(int i=dn;i<n-1;i+=2){
		q.push_back(A[0]);
		q.push_back(i);
		q.push_back(A[1]);
		q.push_back(i+1);
		int v=use_machine(q);
		q.clear();
		if(v%2==0)
			A.push_back(i+1);
		else
			B.push_back(i+1);
		if(v<=1)
			A.push_back(i);
		else
			B.push_back(i+1);
		if(A.size()>=H || B.size()>=H)
			break;
	}
	q.clear();
	if(bl){
		swap(A,B);
		bl=0;
	}
	if(A.size()<B.size()){
		swap(A,B);
		bl=1;
	}
	int cntA=A.size(),cntB=B.size();
	for(int i=(A.size()+B.size());i<n;i+=H){
		q.clear();
		for(int j=i;j<min(i+H,n);j++){
			q.push_back(A[j-i]);
			q.push_back(j);
		}
		int v=use_machine(q)+1;
		cntB+=v/2;
	}
	cntA=n-cntB;
	if(bl)
		swap(cntB,cntA);
	return cntA;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 1 ms 344 KB Duplicate value 4 in the query array.
7 Halted 0 ms 0 KB -