Submission #702671

#	Time	Username	Problem	Language	Result	Execution time	Memory
702671		onjo0127	Rarest Insects (IOI22_insects)	C++17	100 / 100	81 ms	308 KiB

insects

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

int in[2009];

int min_cardinality(int N) {
	int c = 0, g = 0;
	for(int i=0; i<N; i++) {
		move_inside(i);
		int x = press_button();
		if(x == 2) move_outside(i);
		else ++g, in[i] = 1;
	}
	c = g;
	int l = 2, r = N/g, p = 1;
	while(l <= r) {
		int m = l+r >> 1;
        if(r-l > 5) ++m;
		if(m < p) for(int j=0; j<N; j++) if(in[j] > m) {
			move_outside(j);
			in[j] = 0;
			--c;
		}
		for(int j=0; j<N; j++) if(!in[j]) {
			move_inside(j);
			int x = press_button();
			if(x == m+1) move_outside(j);
			else ++c, in[j] = m;
		}
		if(g*m != c) {
			r = m-1;
			for(int j=0; j<N; j++) if(!in[j]) in[j] = -1;
		}
		else l = m+1;
		p = m;
	}
	return r;
}

Compilation message (stderr)

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

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