Submission #1117446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117446		StefanSebez	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	417 ms	940 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;
		}
	}*/
	int l=1,r=n/S+2;
	while(l<=r){
		int mid=l+r>>1;
		while(vals.size())move_outside(vals.back()),vals.pop_back();
		for(int i=0;i<n;i++){
			vals.pb(i);move_inside(i);
			if(press_button()>mid) vals.pop_back(),move_outside(i);
		}
		if(vals.size()>=mid*S){res=mid;l=mid+1;}
		else r=mid-1;
	}
	return res;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid=l+r>>1;
      |           ~^~
insects.cpp:55:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if(vals.size()>=mid*S){res=mid;l=mid+1;}
      |      ~~~~~~~~~~~^~~~~~~
insects.cpp:58:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  return res;
      |         ^~~

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