제출 #1060121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1060121		AmirAli_H1	드문 곤충 (IOI22_insects)	C++17	0 / 100	35 ms	1624 KiB

insects

// In the name of Allah

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

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

#define		endl				'\n'
#define		sep					' '
#define		F					first
#define		S					second
#define		Mp					make_pair
#define		pb					push_back
#define		all(x)				(x).begin(),(x).end()
#define		len(x)				((ll) (x).size())

const int maxn = 2000 + 4;

int n, k, sz, res;
set<int> st; vector<int> ls;
int M[maxn], Mx[maxn];

void addx(int j) {
	st.insert(j); move_inside(j);
}

void delx(int j) {
	st.erase(j); move_outside(j);
}

int askx() {
	return press_button();
}

void del_all() {
	while (!st.empty()) {
		int j = *st.begin();
		delx(j);
	}
}

void cal_sz() {
	sz = 0;
	for (int i = 0; i < n; i++) {
		if (!M[i]) sz++;
	}
}

void checkx(ll R) {
	del_all();
	fill(Mx, Mx + n, 0); int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (M[i]) continue;
		addx(i);
		if (askx() > R) delx(i);
		else {
			Mx[i] = 1; cnt++;
		}
	}
	if (cnt == k * R) {
		res += R;
		for (int i = 0; i < n; i++) {
			if (M[i]) continue;
			if (Mx[i]) M[i] = 1;
		}
	}
	else {
		del_all();
		for (int i = n - 1; i >= 0; i--) {
			if (M[i]) continue;
			if (!Mx[i]) {
				M[i] = 1;
				addx(i);
				if (askx() > 1) delx(i);
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			if (M[i]) continue;
			addx(i);
			if (askx() > 1) M[i] = 1;
			delx(i);
		}
	}
	
	cal_sz();
}

int min_cardinality(int N) {
	n = N; sz = n;
	
	for (int i = 0; i < n; i++) {
		addx(i);
		if (askx() > 1) delx(i);
	}
	for (int j : st) {
		ls.pb(j); M[j] = 1;
	}
	k = len(ls);
	
	res += 1; cal_sz();
	while (sz >= k) {
		int h = (sz / k);
		checkx((h + 1) / 2);
	}
	
	return res;
}

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