Submission #1057785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057785		fuad27	드문 곤충 (IOI22_insects)	C++17	52.70 / 100	106 ms	944 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
	int distcnt = 0;
	set<int> idxs;
	for(int i = 0;i<N;i++) {
		move_inside(i);
		if(press_button() <= 1){
			idxs.insert(i);
			distcnt++;
			continue;
		}
		move_outside(i);
	}
	int ans=1;
	int prev = 1;
	int lo = 2, hi = N/distcnt;
	while(lo <= hi) {
		int mid = (lo+hi)/2;
		if(prev < mid) {
			for(int j = 0;j<N;j++) {
				if(idxs.find(j)!=idxs.end())continue;
				move_inside(j);
				if(press_button() <= mid) {
					idxs.insert(j);
					continue;
				}
				move_outside(j);
			}
		}
		else {
			do {
				move_outside(*(--idxs.end()));
				idxs.erase(--idxs.end());
			}while(press_button() > mid);
			for(int j = 0;j<N;j++) {
				if(idxs.find(j)!=idxs.end())continue;
				move_inside(j);
				if(press_button() <= mid) {
					idxs.insert(j);
					continue;
				}
				move_outside(j);
			}
		}
		if(idxs.size() == distcnt*mid) {
			lo = mid+1;
			ans=mid;
		}
		else {
			hi=mid-1;
		}
		prev=mid;
	}
	return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:47:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   if(idxs.size() == distcnt*mid) {
      |      ~~~~~~~~~~~~^~~~~~~~~~~~~~

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