제출 #1229616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229616		LeonidCuk	Rarest Insects (IOI22_insects)	C++20	99.76 / 100	15 ms	424 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int sum=0,n,k;
void vnesi(int i)
{
    move_inside(i);
    sum++;
}
void izvadi(int i)
{
    move_outside(i);
    sum--;
}
bool vidi(vector<int>&v,int m)
{
    vector<int>v1,v2;
    for(int i=0;i<v.size();i++)
    {
        vnesi(v[i]);
        if(press_button()>m)
        {
            izvadi(v[i]);
            v2.push_back(v[i]);
        }
        else
        {
            v1.push_back(v[i]);
        }
    }
    if(k*m==sum)
    {
        v=v2;
        return true;
    }
    else
    {
        for(int i=0;i<v1.size();i++)izvadi(v1[i]);
        v=v1;
        return false;
    }
}
int min_cardinality(int N)
{
    n=N;
    vector<int>v;
    for(int i=0;i<n;i++)
    {
        vnesi(i);
        if(press_button()>1)
        {
            izvadi(i);v.push_back(i);
        }
    }
    k=sum;
    int l=1,r=n/sum;
    while(l+1<r)
    {
        int m=(l+r)/2;
        if(vidi(v,m))
        {
            l=m;
        }
        else
        {
            r=m-1;
        }
    }
    if(l+1==r)
    {
        if(vidi(v,r))l=r;
    }
    return l;
}

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