제출 #1170755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170755		thelegendary08	드문 곤충 (IOI22_insects)	C++17	10 / 100	43 ms	428 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define f0r(i,n) for(int i = 0;  i< n; i++)
#define mp make_pair
#define pii pair<int,int>
#define vb vector<bool>
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
#define push(x); move_inside(x); v[x] = 1;
#define pull(x); move_outside(x); v[x] = 0;
using namespace std;
vector<bool>v;
vi rep;
int n;
int solve(int l, int r, int y){
	// cout<<y<<' '<<'y'<<'\n';
	// cout<<l<<' '<<r<<'\n';
	int lo = l; 
	int hi = r;
	
	while(lo < hi){
		int mid = (lo + hi) / 2;
		vb cur(n);
		f0r(i, mid + 1){
			cur[rep[i]] = 1;
		}
		cur[y] = 1;
		f0r(i,n){
			if(v[i] && (!cur[i])){pull(i);}
			else if((!v[i]) && cur[i]){push(i);}
		}
		// vout(v);
		int x = press_button();
		if(x == 2){
			hi = mid;
		}
		else{
			lo = mid + 1;
		}
	}
	return lo;
}
int min_cardinality(int n) {
	::n = n;
	v.resize(n);
	vi col(n, -1);
	int cur = 1;
	col[0] = 0;
	rep.resize(n);
	f0r(i,n) rep[i] = 0;
	rep[0] = 0;
	FOR(ii, 1, n){
		vb cura(n);
		FOR(i, 0, cur){
			cura[rep[i]] = 1;
		}
		cura[ii] = 1;
		f0r(i,n){
			if(v[i] && (!cura[i])){pull(i);}
			else if((!v[i]) && cura[i]){push(i);}
		}
		// vout(v);
		int x = press_button();
		if(x == 1){
			// cout<<"HJ"<<'\n';
			col[ii] = cur;
			rep[cur] = ii;
			cur++;
		}
		else{
			// cout<<ii<<' '<<"ii"<<'\n';
			int nc = solve(0, cur - 1, ii);
			col[ii] = nc;
		}
		
		
	}
	// vout(rep);
	// vout(col);
	vi cnt(cur + 1);
	f0r(i, n)cnt[col[i]]++;
	int ans = 1e9;
	f0r(i, cur){
		ans = min(ans, cnt[i]);
	}
	return ans;
}

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