Submission #638284

#	Time	Username	Problem	Language	Result	Execution time	Memory
638284		jamezzz	Rarest Insects (IOI22_insects)	C++17	60.32 / 100	149 ms	636 KiB

insects

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

#define maxn 2005
#define pf printf

mt19937 rng(218);

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

void dnc(int l,int r){
	if(2*lef>rem)return;
	if(l==r){
		num[l]=query[l].size();
		--lef;
		rem-=num[l]+1;
		return;
	}
	if(query[l].empty())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();
	shuffle(uni.begin(),uni.end(),rng);
	for(int x:multi)query[0].push_back(x);
	cur=n-1;
	rem=N,lef=n;
	dnc(0,n-1);

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

Compilation message (stderr)

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

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