제출 #672124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672124		tbzard	드문 곤충 (IOI22_insects)	C++17	95.73 / 100	71 ms	424 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){
    vector<int> v;
    for(int i=0;i<n;i++){
        move_inside(i);
        int r = press_button();
        if(r == 2) move_outside(i);
        else{
            v.push_back(i);
            vis[i] = 1;
        }
    }

    int ans = n/(int)v.size();
    int lo = 1, hi = ans-1;
    vector<int> add;
    int cnt = 0;
    int k = 1;
    while(lo <= hi){
        int mid = (lo+hi)/2;

        if(mid >= k){
            for(int i=0;i<n;i++){
                if(vis[i]) continue;
                if(cnt == (int)v.size()*mid){
                    break;
                }

                move_inside(i);
                int r = press_button();
                k = r;
                if(r == mid+2){
                    move_outside(i);
                    k = r-1;
                }
                else{
                    vis[i] = 1;
                    add.push_back(i);
                    cnt++;
                }
            }
        }
        else{
            vector<int> out;
            while(!add.empty()){
                int i = add.back();

                move_outside(i);
                vis[i] = 0;
                add.pop_back();
                cnt--;
                out.push_back(i);
                int r = press_button();
                k = r;
                if(r < mid+2){
                    break;
                }
            }
            for(int j=0;j<(int)out.size();j++){
                int i = out[j];
                if(vis[i]) continue;
                if(cnt == (int)v.size()*mid){
                    break;
                }

                move_inside(i);
                int r = press_button();
                k = r;
                if(r == mid+2){
                    move_outside(i);
                    k = r-1;
                }
                else{
                    vis[i] = 1;
                    add.push_back(i);
                    cnt++;
                }

            }
        }

        if(cnt < (int)v.size()*mid) ans = mid, hi = mid-1;
        else lo = mid+1;
    }

    return ans;
}

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