Submission #630829

#	Time	Username	Problem	Language	Result	Execution time	Memory
630829		uncripted	Rarest Insects (IOI22_insects)	C++17	10 / 100	413 ms	324 KiB

insects

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

#define pb push_back	
vector<int> v;
void cler(){
	for(int i=0; i<v.size(); i++){
		move_outside(v[i]);
	}
}
int min_cardinality(int N) {
	int n=0;

	for(int i=0; i<N; i++){
		move_inside(i);
		n++;
		if(press_button()>1){
			move_outside(i);
			n--;
		}else{
			v.pb(i);
		}
	}
	if(n<=70){
		vector<int> dif;
		int m[N+1];
		dif.pb(0);
		for(int i=0; i<N; i++){
			m[i]=0;
		}
		m[0]=1;
		for(int i=1; i<N; i++){	
		move_inside(i);
		bool f=false;
			for(int j=0; j<dif.size(); j++){
			
			
				move_inside(dif[j]);
			//	cout<<press_button()<<" "<<i<<endl;
				if(press_button()>1){
					m[j]++;
					f=true;
					move_outside(dif[j]);
					break;
				}
				move_outside(dif[j]);
			}
			if(f==false){
				dif.pb(i);
				m[dif.size()-1]++;
			}
			move_outside(i);
		}
		int minn=INT_MAX;
		for(int i=0; i<dif.size(); i++){
	//		cout<<m[i]<<" m "<<dif[i]<<endl;
			minn=min(minn, m[i]);
		}
		return minn;
	}else{
		int l=1,r=2000;
		while(l<r){
			cler();
			int m=(l+r+1)/2;
		//	cout<<m<<endl;
			int siz=0;
		
			for(int i=0; i<N; i++){
				move_inside(i);	
				siz++;
				if(press_button()>m){
					move_outside(i);
					siz--;
				}
			}
			if(siz!=n*m){
				r=m-1;
			}else{
				l=m;
			}
		}
		return l;	
	}

}

Compilation message (stderr)

insects.cpp: In function 'void cler()':
insects.cpp:8:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for(int i=0; i<v.size(); i++){
      |               ~^~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int j=0; j<dif.size(); j++){
      |                 ~^~~~~~~~~~~
insects.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i=0; i<dif.size(); i++){
      |                ~^~~~~~~~~~~

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