Submission #1170753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170753		thelegendary08	Rarest Insects (IOI22_insects)	C++17	10 / 100	28 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 mid = (l + r) / 2;
	vb cur(n);
	FOR(i, l, 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){
		if(l == mid){
			return l;
		}
		else{
			return solve(l, mid, y);
		}
	}
	else{
		if(mid + 1 == r)return r;
		else{
			return solve(mid + 1, r, y);
		}
	}
}
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