Submission #1117442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117442		StefanSebez	Rarest Insects (IOI22_insects)	C++17	25 / 100	775 ms	596 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
int min_cardinality(int n) {
	vector<int>vals;
	for(int i=0;i<n;i++){
		vals.pb(i);move_inside(i);
		if(press_button()==2) vals.pop_back(),move_outside(i);
	}
	//for(auto i:vals) printf("%i ",i);printf("\n");
	int S=vals.size(),res;
	if(S*S<=n){
		while(vals.size())move_outside(vals.back()),vals.pop_back();
		bool was[n+10]={false};
		res=n+10;
		for(int i=0;i<n;i++){
			if(was[i]) continue;
			move_inside(i);
			int ct=1;
			for(int j=i+1;j<n;j++){
				move_inside(j);
				if(press_button()==2) was[j]=true,ct++;
				move_outside(j);
			}
			move_outside(i);
			res=min(res,ct);
		}
	}
	else{
		res=0;
		bool was[n+10]={false};
		while(++res){
			while(vals.size())move_outside(vals.back()),was[vals.back()]=true,vals.pop_back();
			for(int i=0;i<n;i++){
				if(was[i]) continue;
				vals.pb(i);move_inside(i);
				if(press_button()==2) vals.pop_back(),move_outside(i);
			}
			if(vals.size()!=S) break;
		}
	}
	return res;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:44:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |    if(vals.size()!=S) break;
      |       ~~~~~~~~~~~^~~

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