제출 #631503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631503		fuad27	드문 곤충 (IOI22_insects)	C++17	0 / 100	187 ms	340 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
	vector<int> idx_type;
	idx_type.push_back(0);
	move_inside(0);
	for(int i = 1;i<N;i++) {
		move_inside(i);
		int val=press_button();
		if(val == 2)move_outside(i);
		else idx_type.push_back(i);
	}
	for(int i:idx_type) {
		move_outside(i);
	}
	vector<int> l(N, 0), r(N, idx_type.size()-2), res(N, idx_type.size()-1);
	for(int i = 0;i<idx_type.size();i++) {
		r[idx_type[i]]=i;
		l[idx_type[i]]=i+1;
		res[i]=i;
	}
	vector<pair<int,int>> que;
	int tmp=0;
	while(1) {
		que.clear();
		bool check=false;
		for(int i = 0;i<N;i++) {
			if(l[i]<=r[i]) {
				que.push_back({(r[i]+l[i])/2, i});
				check=true;
			}
		}
		int cnt=tmp;
		sort(que.begin(), que.end());
		for(int i = 0;i<que.size();i++) {
			int mid = que[i].first;
			while(cnt > mid+1) {
				move_outside(idx_type[--cnt]);
			}
			while(cnt <= mid) {
				move_inside(idx_type[cnt++]);
			}
			move_inside(que[i].second);
			int val=press_button();
			//~ cout << que[i].second << " " << mid << ": " << val-1<< endl;
			if(val == 2) {
				r[que[i].second]=mid-1;
				res[que[i].second]=mid;
			}
			else {
				l[que[i].second]=mid+1;
			}
			move_outside(que[i].second);
		}
		tmp=cnt;
		if(!check)break;
	}
	vector<int> cnt(N+1, 0);
	for(int i = 0;i<N;i++) {
		//~ if(res[i]==-1)res[i]=idx_type.size();s
		//~ cout << res[i] << " ";
		cnt[idx_type[res[i]]]++;
	}
	//~ cout << endl;
	//~ cout << endl;
	int ans=20000;
	for(int i = 0;i<N;i++) {
		if(cnt[i]==0)continue;
		ans=min(ans, cnt[i]);
	}
	return ans;
}

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

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:18:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0;i<idx_type.size();i++) {
      |                ~^~~~~~~~~~~~~~~~
insects.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i = 0;i<que.size();i++) {
      |                 ~^~~~~~~~~~~

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