Submission #1057911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057911		tolbi	Rarest Insects (IOI22_insects)	C++17	58.42 / 100	88 ms	968 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
/*
void move_inside(int i);
void move_outside(int i);
int press_button();
*/
int mid(pair<int,int> &pr){
	return (pr.first+pr.second)/2;
}
int min_cardinality(int N) {
	vector<int> unik;
	vector<pair<int,int>> dec(N,{-1,-1});
	vector<int> ans(N,-1);
	for (int i = 0; i < N; i++){
		move_inside(i);
		if (press_button()>1){
			move_outside(i);
			dec[i]={0,23};
		}
		else {
			ans[i]=unik.size();
			unik.push_back(i);
		}
	}
	vector<vector<int>> pbs(unik.size());
	for (int i = 0; i < N; ++i)
	{
		if (dec[i].first!=-1) {
			dec[i].second=unik.size()-1;
			pbs[mid(dec[i])].push_back(i);
		}
	}
	int kalan = N-unik.size();
	int turn = 0;
	while (kalan>0){
		if (turn==0){
			for (int i = (int)unik.size()-1; i >= 0; i--){
				while (pbs[i].size()){
					int node = pbs[i].back();
					pbs[i].pop_back();
					move_inside(node);
					if (press_button()>1){
						dec[node].second=i;
					}
					else {
						dec[node].first=i+1;
					}
					move_outside(node);
				}
				move_outside(unik[i]);
			}
		}
		else {
			for (int i = 0; i < unik.size(); i++){
				move_inside(unik[i]);
				while (pbs[i].size()){
					int node = pbs[i].back();
					pbs[i].pop_back();
					move_inside(node);
					if (press_button()>1){
						dec[node].second=i;
					}
					else {
						dec[node].first=i+1;
					}
					move_outside(node);
				}
			}
		}
		turn=1-turn;
		for (int i = 0; i < N; i++){
			if (ans[i]==-1){
				if (dec[i].first==dec[i].second){
					ans[i]=dec[i].first;
					kalan--;
				}
				else {
					pbs[mid(dec[i])].push_back(i);
				}
			}
		}
	}
	map<int,int> mp;
	for (int i = 0; i < N; ++i)
	{
		mp[ans[i]]++;
	}
	int ns = N;
	for (auto it : mp){
		ns = min(ns,it.second);
	}
	return ns;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:56:22: 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 < unik.size(); i++){
      |                    ~~^~~~~~~~~~~~~

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