Submission #837435

#	Time	Username	Problem	Language	Result	Execution time	Memory
837435		NothingXD	Rarest Insects (IOI22_insects)	C++17	55.93 / 100	143 ms	484 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e3 + 10;
const int lg = 20;
int l[maxn], r[maxn], cnt[maxn];
vector<int> a, b;
vector<int> idx[maxn];

bool check_empty(int x){
	for (int i = x; i < a.size(); i++){
		if (!idx[i].empty()) return false;
	}
	return true;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int min_cardinality(int N) {
	int n = N;
	vector<int> A;
	for (int i = 0; i < n; i++) A.push_back(i);
	shuffle(all(A), rng);
	for (auto i: A){
		move_inside(i);
		if (press_button() == 2){
			move_outside(i);
			l[b.size()] = -1;
			r[b.size()] = a.size();
			b.push_back(i);
			continue;
		}
		//debug(i);
		a.push_back(i);
	}
	for (int i = 0; i < a.size(); i++){
		move_outside(a[i]);
	}
	for (int i = 0; i < b.size(); i++){
		if (l[i] + 1 < r[i]){
			int mid = (l[i] + r[i]) >> 1;
			idx[mid].push_back(i);
		}
	}
	//debug(a.size(), b.size());
	while(!check_empty(0)){
		int j;
		for (j = 0; !check_empty(j) && j < a.size(); j++){
			move_inside(a[j]);
			for (auto x: idx[j]){
				move_inside(b[x]);
			//	debug(j, x, b[x], press_button());
				if (press_button() == 2) r[x] = j;
				else l[x] = j;
				if (l[x] + 1 < r[x]){
					int mid = (l[x] + r[x]) >> 1;
					idx[mid].push_back(x);
				}
				move_outside(b[x]);
			}
			idx[j].clear();
		}
		//for (int i = 0; i < b.size(); i++) debug(i, l[i], r[i]);
		for (int i = 0; i < j; i++){
			move_outside(a[i]);
		}
	}

	for (int i = 0; i < b.size(); i++){
		cnt[r[i]]++;
	}
	int ans = n;
	for (int i = 0; i < a.size(); i++){
		ans = min(ans, cnt[i]);
	//	debug(cnt[i]);
	}
	return ans+1;
}

Compilation message (stderr)

insects.cpp: In function 'bool check_empty(int)':
insects.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = x; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0; i < b.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:67:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (j = 0; !check_empty(j) && j < a.size(); j++){
      |                                  ~~^~~~~~~~~~
insects.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i = 0; i < b.size(); i++){
      |                  ~~^~~~~~~~~~
insects.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~

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