Submission #798504

#	Time	Username	Problem	Language	Result	Execution time	Memory
798504		aymanrs	Rarest Insects (IOI22_insects)	C++17	53.20 / 100	106 ms	336 KiB

insects

#include<bits/stdc++.h>
const int MOD = 1e9+7;
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N){
	int t = 0;
	vector<int> v;
	bool vis[N] = {false};
	for(int i = 0;i < N;i++){
		move_inside(i);
		if(press_button() == 2){
			move_outside(i);
		} else {
			vis[i] = true;
			t++;
			v.push_back(i);
		}
	}
	int ans = N;
	if(t <= 2){
		for(int i : v) if(i) move_outside(i);
		for(int i : v){
			if(i) move_inside(i);
			t = 1;
			for(int j = i+1;j < N;j++){
				if(vis[j]) continue;
				move_inside(j);
				if(press_button() == 2){
					t++;
					vis[j] = true;
				}
				move_outside(j);
			}
			ans = min(ans, t);
		}
		return ans;
	}
	int l = 1, r = N/t, b = 1, m;
	while(l <= r){
		m = l+r>>1;
		int rb = 0;
		bool s[N] = {false};
		for(int i = 0;i < N;i++){
			if(vis[i]) continue;
			move_inside(i);
			if(press_button() > m){
				rb++;
				move_outside(i);
			} else s[i] = true;
		}
		if(rb == N-t*m) {
			b = m;
			l = m+1;
            for(int i = 0;i < N;i++) if(s[i]) vis[i] = true;
		} else {
			if(l <= r) for(int i = 0;i < N;i++) if(s[i]) move_outside(i);
			r = m-1;
		}
	}
	return b;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:42:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   m = l+r>>1;
      |       ~^~

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