Submission #1061962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061962		jerzyk	Rarest Insects (IOI22_insects)	C++17	0 / 100	8 ms	600 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
bool out[N], czy[N];
vector<int> cur;
int lft, dif;

int findDif(int n)
{
    for(int i = 0; i < n; ++i)
    {
        move_inside(i);
        cur.pb(i);
        if(press_button() > 1)
        {
            cur.pop_back();
            move_outside(i);
        }
    }
    int ans = cur.size();
    for(int i = 0; i < (int)cur.size(); ++i)
    {
        move_outside(cur[i]);
    }
    cur.clear();
    return ans;
}

int Check(int x, int n)
{
    int ans = 0, xd = 0;
    for(int i = 0; i < n; ++i)
    {
        if(out[i]) continue;
        move_inside(i);
        czy[i] = true;
        ans = press_button();
        ++xd;
        if(ans > x + 1)
        {
            --xd;
            --ans;
            czy[i] = false;
            move_outside(i);
        }
    }
    //cerr << "xddd " << ans << "\n";
    int cp = ans;
    if(xd == dif * (x + 1))
        ans = x + 1;
    else
        ans = min(ans, x);
    for(int i = 0; i < n; ++i)
    {
        if(out[i]) continue;
        if(czy[i])
        {
            move_outside(i);
            czy[i] = false;
            if(press_button() < cp)
            {
                move_inside(i);
                czy[i] = true;
            }
        }else
        {
            move_inside(i);
            czy[i] = true;
            if(press_button() == cp)
            {
                czy[i] = false;
                move_outside(i);
            }else
                ++cp;
        }
    }

    for(int i = 0; i < n; ++i)
    {
        if(out[i]) continue;
        if(!czy[i]) continue;
        out[i] = true;
    }
    --dif;
    lft -= cp;
    return ans;
}

int BS(int maks, int n)
{
    int p = 1, k = maks;
    while(p < k)
    {
        int s = (p + k) / 2;
        if(dif == 1)
            return lft;
        int x = Check(s, n);
        if(x > s)
            p = s + 1;
        else
            k = s;
        k = min(k, lft / dif);
    }
    return p;
}

int min_cardinality(int n)
{
    dif = findDif(n);
    lft = n;
    //cerr << "dif " << dif << "\n";
    int m = (n / dif);
    int ans = BS(m, n);
    return ans;
}

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