Submission #638282

#	Time	Username	Problem	Language	Result	Execution time	Memory
638282		jamezzz	Rarest Insects (IOI22_insects)	C++17	60.34 / 100	153 ms	620 KiB

insects

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

#define maxn 2005
#define pf printf

int num[maxn],cur;
vector<int> uni,multi,query[maxn];
deque<pair<int,int>> dq,dq2;

void dnc(int l,int r){
	if(query[l].empty())return;
	if(l==r){
		num[l]=query[l].size();
		return;
	}
	vector<int> tl,tr;
	int m=(l+r)>>1;
	while(cur<m)move_inside(uni[++cur]);
	while(m<cur)move_outside(uni[cur--]);
	for(int x:query[l]){
		move_inside(x);
		if(press_button()==2)tl.push_back(x);
		else tr.push_back(x);
		move_outside(x);
	}
	swap(tl,query[l]);
	swap(tr,query[m+1]);
	dnc(l,m);
	dnc(m+1,r);
}

int min_cardinality(int N){
	for(int i=0;i<N;++i){
		move_inside(i);
		if(press_button()==1)uni.push_back(i);
		else move_outside(i),multi.push_back(i);
	}
	int direction=0;
	int n=uni.size();
	if(2*n>N)return 1;
	for(int x:multi)query[0].push_back(x);
	cur=n-1;
	dnc(0,n-1);

	int ans=N;
	for(int i=0;i<n;++i)ans=min(ans,num[i]+1);
	return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:40:6: warning: unused variable 'direction' [-Wunused-variable]
   40 |  int direction=0;
      |      ^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 35.34 / 75