Submission #1335753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335753		yhkhoo	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	20 ms	464 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

#define qry() press_button()
#define vi basic_string<int>
#define cnt count(cur.begin(), cur.end(), 1)
vector<int> o;

void in(int x){
    move_inside(o[x]);
}

void out(int x){
    move_outside(o[x]);
}

int min_cardinality(int n) {
    mt19937 rnd(6767);
    o.clear();
    o.resize(n);
    for(int i=0; i<n; i++){
        o[i] = i;
    }
    shuffle(o.begin(), o.end(), rnd);

    vi f, nf;
    for(int i=0; i<n; i++){
        in(i);
        if(qry() == 1){
            f += i;
        }
        else{
            out(i);
            nf += i;
        }
    }
    int l = 1, r = n / f.size(), m;
    vector<bool> cur(n), good(n), prev(n), bad(n);
    bool down = 0;
    while(l < r){
        m = (l+r+1)/2;
        for(auto i: nf){
            if(bad[i]) continue;
            if(down){
                if(prev[i] && (!good[i])){
                    in(i);
                    if(qry() > m){
                        out(i);
                        cur[i] = 0;
                    }
                    else{
                        cur[i] = 1;
                    }
                }
            }
            else{
                if(!good[i]){
                    in(i);
                    if(qry() > m){
                        out(i);
                        cur[i] = 0;
                    }
                    else{
                        cur[i] = 1;
                    }
                }
            }
        }
        prev = cur;
        if(cnt < (m-1) * f.size()){ // m too big
            r = m-1;
            down = 1;
            for(auto i: nf){
                if(!cur[i]){
                    bad[i] = 1;
                }
                if(cur[i] && (!good[i])){
                    out(i);
                    cur[i] = 0;
                }
            }
        }
        else{ // m ok
            l = m;
            down = 0;
            for(auto i: nf){
                if(cur[i]) good[i] = 1;
            }
        }
    }
    return l;
}

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