Submission #1335733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335733		yhkhoo	드문 곤충 (IOI22_insects)	C++17	93.68 / 100	23 ms	448 KiB

insects

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

#define qry() press_button()
#define in(x) move_inside(x)
#define out(x) move_outside(x)
#define vi basic_string<int>

int min_cardinality(int n) {
    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);
    bool down = 0;
    while(l < r){
        m = (l+r+1)/2;
        /*cerr << m << '\n';
        if(m){
            for(auto i: nf){
                if(cur[i]) cerr << i << ' ';
            }
        }
        cerr << '\n';*/
        for(auto i: nf){
            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;
                    }
                }
            }
        }
        int cnt = count(cur.begin(), cur.end(), 1);
        prev = cur;
        if(cnt != (m-1) * f.size()){ // m too big
            r = m-1;
            down = 1;
            for(auto i: nf){
                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: 68.68 / 75