Submission #1136688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136688		Saul0906	Rarest Insects (IOI22_insects)	C++20	100 / 100	14 ms	432 KiB

insects

#include "insects.h"
#include <vector>
#include <bits/stdc++.h>
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define repr(a,b,c) for(ll a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define mid ((l+r)>>1)
#define ppb pop_back
#define all(a) a.begin(), a.end()

using namespace std;
using vi = vector<int>;

mt19937 rnd(1e9+7);

int min_cardinality(int n) {
	vi a, b, c, d;
	rep(i,0,n){
		move_inside(i);
		a.pb(i);
		if(press_button()==2){
			move_outside(i);
			a.ppb();
			b.pb(i);
		}
	}
	int l=1, r=n/a.size(), y=a.size();
	repa(e,a) move_outside(e);
	while(l<=r){
		shuffle(all(b),rnd);
		repa(e,b){
			if(y==mid*a.size()){
				d.pb(e);
				continue;
			}
			move_inside(e);
			c.pb(e);
			y++;
			if(press_button()==mid){
				move_outside(e);
				c.ppb();
				d.pb(e);
				y--;
			}
		}
		if(y==mid*a.size()){
			y=mid*a.size();
			l=mid+1;
			b=d;
			c.clear();
			d.clear();
		}else{
			repa(e,c) move_outside(e), y--;
			r=mid-1;
			b=c;
			c.clear();
			d.clear();
		}
	}
	return r;
}

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