Submission #797746

#	Time	Username	Problem	Language	Result	Execution time	Memory
797746		HaroldVemeno	Rarest Insects (IOI22_insects)	C++17	99.78 / 100	54 ms	296 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int min_cardinality(int n) {
    vector<bool> skip(n);
    vector<bool> box(n);
    int s = 0;
    for(int i = 0; i < n; ++i) {
        box[i] = true;
        move_inside(i);
        ++s;
        int c = press_button();
        if(c > 1) {
            move_outside(i);
            --s;
            box[i] = false;
        }
    }
    D(s)
    if(s == n) return 1;
    for(int i = 0; i < n; ++i) {
        if(box[i]) {
            move_outside(i);
            skip[i] = true;
        }
    }
    int rm = 1;
    int f = 1;
    int t = n/s;
    while(f != t) {
        int m = (f+t+1)/2;
        D(f)
        D(t)
        D(m)
        int ss = 0;
        for(int i = 0; i < n; ++i) {
            if(skip[i]) continue;
            box[i] = true;
            ++ss;
            move_inside(i);
            int c = press_button();
            if(c > m-rm) {
                move_outside(i);
                box[i] = false;
                --ss;
            }
        }
        D(ss)
        if(ss == s*(m-rm)) {
            rm = m;
            f = m;
            for(int i = 0; i < n; ++i) {
                if(box[i]) skip[i] = true;
            }
        } else {
            t = m-1;
            for(int i = 0; i < n; ++i) {
                if(!box[i]) skip[i] = true;
            }
        }
        for(int i = 0; i < n; ++i) {
            if(box[i]) move_outside(i);
            box[i] = false;
        }
    }
    return f;
}

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