제출 #798517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
798517		aymanrs	드문 곤충 (IOI22_insects)	C++17	99.89 / 100	54 ms	352 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;
	bool broke[N] = {false};
	while(l <= r){
		m = l+r>>1;
		int rb = 0;
		bool s[N] = {false};
		int ind = N;
		for(int i = 0;i < N;i++){
			if(vis[i]) continue;
			if(broke[i]){
				rb++;
			} else {
			move_inside(i);
			if(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 = m-1;
			if(l <= r) {
				for(int i = 0;i < ind;i++) {
					if(s[i]) move_outside(i);
					else broke[i] = true;
				}
			}
		}
	}
	return b;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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