Submission #830605

#	Time	Username	Problem	Language	Result	Execution time	Memory
830605		FatihSolak	Rarest Insects (IOI22_insects)	C++17	76.10 / 100	109 ms	320 KiB

insects

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

int min_cardinality(int N){
	mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
	vector<int> ord;
	for(int i = 0;i<N;i++){
		ord.push_back(i);
	}
	shuffle(ord.begin(),ord.end(),rng);
	vector<int> v;
	int now = 0;
	int dif = 0;
	auto add = [&](int x){
		v.push_back(x);
		move_inside(ord[x]);
		now = press_button();
	};
	auto del = [&](){
		move_outside(ord[v.back()]);
		v.pop_back();
		now = press_button();
	};
	auto del2 = [&](){
		move_outside(ord[v.back()]);
		v.pop_back();
		now--;
	};
	auto del3 = [&](){
		move_outside(ord[v.back()]);
		v.pop_back();
	};
	add(0);
	dif = 1;
	for(int i = 1;i<N;i++){
		add(i);
		if(now == 2){
			del2();
		}
		else dif++;
	}
	if(dif == 1)
		return N;
	if(dif == 2){
		for(int i = 0;i<N;i++){
			if(find(v.begin(),v.end(),i) == v.end()){
				add(i);
			}
		}
		return N - now;
	}
	if(N/dif > (1<<5) && dif <= 8){
		vector<bool> found(N,0);
		int mini = 1e9;
		for(int i = 0;i<N;i++){
			if(found[i] == 0){
				while(v.size())
					del2();
				now = 0;
				int cnt = 0;
				for(int j = 0;j<N;j++){
					if(found[j])continue;
					add(j);
					if(now != cnt + 1){
						del3();
					}
					else{
						found[j] = 1;
						cnt++;
					}
				}
				mini = min(mini,cnt);
			}
		}
		return mini;
	}
	int l = 1,r = N/dif;
	while(l < r){
		int m = (l + r + 1)/2;
		int tmp = now;
		press_button();
		assert(now == tmp);
		if(now < m){
			for(int i = 0;i<N;i++){
				if(v.size() == m * dif || v.size() + N - i < m * dif)
					break;
				if(find(v.begin(),v.end(),i) == v.end()){
					add(i);
					if(now > m)
						del2();
				}
			}
		}
		else{
			while(now > m){
				del();
			}
			for(int i = 0;i<N;i++){
				if(v.size() == m * dif || v.size() + N - i < m * dif)
					break;
				if(find(v.begin(),v.end(),i) == v.end()){
					add(i);
					if(now > m)
						del2();
				}
			}
		}
		if(v.size() == m * dif){
			l  = m;
		}
		else r = m -1;
	}
	return l;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:86:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |     if(v.size() == m * dif || v.size() + N - i < m * dif)
      |        ~~~~~~~~~^~~~~~~~~~
insects.cpp:86:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |     if(v.size() == m * dif || v.size() + N - i < m * dif)
      |                               ~~~~~~~~~~~~~~~~~^~~~~~~~~
insects.cpp:100:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     if(v.size() == m * dif || v.size() + N - i < m * dif)
      |        ~~~~~~~~~^~~~~~~~~~
insects.cpp:100:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     if(v.size() == m * dif || v.size() + N - i < m * dif)
      |                               ~~~~~~~~~~~~~~~~~^~~~~~~~~
insects.cpp:109:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |   if(v.size() == m * dif){
      |      ~~~~~~~~~^~~~~~~~~~

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