제출 #638271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638271		jamezzz	Rarest Insects (IOI22_insects)	C++17	0 / 100	72 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;
	
	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();
		}
		if(l==r){
			for(int x:query[l])++num[l];
			continue;
		}
		int m=(l+r)>>1;
		while(cur<m)move_inside(++cur);
		while(m<cur)move_outside(cur--);
		vector<int> tl,tr;
		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+r)>>1]);
			}
			if(!tl.empty()){
				dq2.push_front({l,m});
				swap(tl,query[(l+m)>>1]);
			}
			if(l==0){
				direction=1;//forward
				swap(dq,dq2);
			}
		}
		else{//forward
			if(!tl.empty()){
				dq2.push_back({l,m});
				swap(tl,query[(l+m)>>1]);
			}
			if(!tr.empty()){
				dq2.push_back({m+1,r});
				swap(tr,query[(m+1+r)>>1]);
			}
			if(r==n-1){
				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:35:12: warning: unused variable 'x' [-Wunused-variable]
   35 |    for(int x:query[l])++num[l];
      |            ^

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