Submission #672093

#	Time	Username	Problem	Language	Result	Execution time	Memory
672093		tbzard	Rarest Insects (IOI22_insects)	C++17	0 / 100	0 ms	208 KiB

insects

#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
 
bool vis[2222];
int min_cardinality(int n){
    int ans = 0;
    for(int i=0;i<n;i++){
        move_inside(i);
        int r = press_button();
        if(r > ans) ans = r, vis[i] = 1;
        else move_outside(i);
    }

    for(int i=0;i<n;i++){
        if(vis[i]) move_outside(i);
    }

    int lo = 1, hi = ans-1;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        int cnt = 0;
        for(int i=0;i<n;i++){
            if(vis[i]) move_inside(i), cnt++;
            if(cnt == mid) break;
        }
        for(int i=0;i<n;i++){
            if(!vis[i]) move_inside(i);
        }

        int r = press_button();
        if(r == mid) ans = mid, hi = mid-1;
        else lo = mid+1;

        for(int i=0;i<n;i++){
            if(vis[i]) move_outside(i), cnt--;
            if(cnt == 0) break;
        }
        for(int i=0;i<n;i++){
            if(!vis[i]) move_outside(i);
        }
    }
    return ans;
}

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