Submission #627540

#	Time	Username	Problem	Language	Result	Execution time	Memory
627540		maxcruickshanks	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	70 ms	420 KiB

insects

#include <bits/stdc++.h>
using namespace std;
#include "insects.h"
//taken from https://dmoj.ca/src/4766178
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#define pb push_back
#define fs first
#define sn second
#define ms(a, x) memset(a, x, sizeof(a))
#define SZ(v) ((int) (v).size())
#define ALL(v) (v).begin(), (v).end()
const int INF = 0x3f3f3f3f;
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << (x) << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}

mt19937_64 rng(9438443753);
ll randInt(ll a, ll b){return uniform_int_distribution(a, b)(rng);}

const int CUT = 10;

int solveKillCol(vi vec){
    if(vec.empty()) return INF;
    shuffle(ALL(vec), rng);
    vi newVec;

    int sample = vec[0];
    move_inside(sample);

    for(int a : vec){
        if(a == sample) continue;
        move_inside(a);
        if(press_button() == 1) newVec.pb(a);
        move_outside(a);
    }

    return min(SZ(vec) - SZ(newVec), solveKillCol(newVec));
}

int solve(int n, int typeC, vi vec){
    int lo = 1, hi = n/typeC;

    while(lo < hi){
        int mid = (lo+hi+1)/2;
        vi inMach, outMach;

        for(int a : vec){
            move_inside(a);
            int res = press_button();
            if(res <= mid) inMach.pb(a);
            else move_outside(a), outMach.pb(a);
        }

        if(SZ(inMach) == typeC*(mid-lo)){
            lo = mid;
            vec = outMach;
        }
        else {
            hi = mid-1;
            vec = inMach;
            for(int a : inMach) move_outside(a);
        }
    }

    return lo;
}

int min_cardinality(int n){
    vi inMach, vec;
    FR(i, n){
        move_inside(i);
        int res = press_button();
        if(res == 2) move_outside(i), vec.pb(i);
        else inMach.pb(i);
    }

    int typeC = SZ(inMach);
    /*dbg(typeC);
    dbgArr(inMach.begin(), SZ(inMach));
    dbgArr(vec.begin(), SZ(vec));*/

    if(false){
        for(int a : inMach) move_outside(a), vec.pb(a);
        return solveKillCol(vec);
    }
    else return solve(n, typeC, vec);
}

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