Submission #632545

#	Time	Username	Problem	Language	Result	Execution time	Memory
632545		_Avocado_	Rarest Insects (IOI22_insects)	C++17	0 / 100	51 ms	392 KiB

insects

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

int min_cardinality(int n){
	vector<int>unique(n);
	int unique_cnt = 0;
	for(int i = 0; i<n; ++i){
		move_inside(i);
		int q = press_button();
		if(q == 1){
			unique[i] = 1;
			++unique_cnt;
		}
		else move_outside(i);
	}
	
	int r = n/unique_cnt+1;
	int l = 1;
	vector<int>cur;
	set<int>in_box;
	for(int i = 0; i<n; ++i){
		if(!unique[i]) cur.push_back(i);
		else in_box.insert(i);
	}
	
	vector<int>cnt(n);
	
	while(r-l > 1){
		int m = (r+l)/2;
		vector<int>high, low;
		for(int i = 0; i<cur.size(); ++i){
			if(in_box.size() == m*unique_cnt){
				high.push_back(cur[i]);
				continue;
			}
			if(in_box.find(cur[i]) != in_box.end()) continue;
			move_inside(cur[i]);
			int q = press_button();
			if(q > m){
				high.push_back(cur[i]);
				move_outside(cur[i]);
			}
			else{
				cnt[cur[i]] = q;
				low.push_back(cur[i]);
				in_box.insert(cur[i]);
			}
		}
	
		if(in_box.size() != m*unique_cnt){
			int next_m = (m+l)/2;
			for(int i = 0; i<cur.size(); ++i){
				if(cnt[cur[i]] > next_m){
					move_outside(cur[i]);
					in_box.erase(cur[i]);
				}
			}
			cur = low;
			r = m;
		}
		else{
			cur = high;
			l = m;
		}
	}
			
	return l;	

}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 0; i<cur.size(); ++i){
      |                  ~^~~~~~~~~~~
insects.cpp:33:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |    if(in_box.size() == m*unique_cnt){
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
insects.cpp:51:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   if(in_box.size() != m*unique_cnt){
      |      ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
insects.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int i = 0; i<cur.size(); ++i){
      |                   ~^~~~~~~~~~~

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