제출 #638278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638278		jamezzz	Rarest Insects (IOI22_insects)	C++17	59.04 / 100	151 ms	620 KiB

insects

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

#define maxn 2005
#define pf printf

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

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();
	for(int x:multi)query[0].push_back(x);
	dq.push_back({0,n-1});
	int cur=n-1;
	
	//pf("uni: ");for(int i:uni)pf("%d ",i);pf("\n");
	//pf("multi: ");for(int i:multi)pf("%d ",i);pf("\n");
	
	while(!dq.empty()){
		int l,r;
		if(direction==0){//backwards
			tie(l,r)=dq.back();
			dq.pop_back();
		}
		else{//forwards
			tie(l,r)=dq.front();
			dq.pop_front();
		}
		//pf("query %d %d: ",l,r);
		//for(int x:query[l])pf("%d ",x);
		//pf("\n");
		vector<int> tl,tr;
		int m=(l+r)>>1;
		if(l==r){
			for(int x:query[l])++num[l];
		}
		else{
			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);
			}
		}
		if(direction==0){//backwards
			if(!tr.empty()){
				dq2.push_front({m+1,r});
				swap(tr,query[m+1]);
			}
			if(!tl.empty()){
				dq2.push_front({l,m});
				swap(tl,query[l]);
			}
			if(dq.empty()){
				direction=1;//forward
				swap(dq,dq2);
			}
		}
		else{//forward
			if(!tl.empty()){
				dq2.push_back({l,m});
				swap(tl,query[l]);
			}
			if(!tr.empty()){
				dq2.push_back({m+1,r});
				swap(tr,query[m+1]);
			}
			if(dq.empty()){
				direction=0;//backwards
				swap(dq,dq2);
			}
		}
	}
	int ans=N;
	for(int i=0;i<n;++i)ans=min(ans,num[i]+1);
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:43:12: warning: unused variable 'x' [-Wunused-variable]
   43 |    for(int x:query[l])++num[l];
      |            ^

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