Submission #799240

#	Time	Username	Problem	Language	Result	Execution time	Memory
799240		aymanrs	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	53 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 = 2, r = N/t, b = 1, m, rbm = 0;
	bool broke[N] = {false};
	while(l <= r){
		m = l+r>>1;
		int rb = rbm;
		bool s[N] = {false};
		int ind = N;
		for(int i = 0;i < N;i++){
			if(vis[i]) continue;
			move_inside(i);
			if(i >= m && press_button() > m){
				rb++;
				move_outside(i);
			} else s[i] = true;
			if(rb > N-t*m) {
				ind = i+1;
				break;
			}
		}
		if(rb == N-t*m) {
			b = m;
			l = m+1;
			for(int i = 0;i < N;i++) if(s[i]) vis[i] = true;
		} else {
			r = min(m-1, (N-rb)/t);
			if(l <= r) {
				for(int i = 0;i < ind;i++) {
					if(s[i]) move_outside(i);
					else if (!vis[i]) {
						vis[i] = true;
						rbm++;
					}
				}
			}
		}
	}
	return b;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:43:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   m = l+r>>1;
      |       ~^~
insects.cpp:41:7: warning: unused variable 'broke' [-Wunused-variable]
   41 |  bool broke[N] = {false};
      |       ^~~~~

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