제출 #1062150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062150		jerzyk	드문 곤충 (IOI22_insects)	C++17	53.16 / 100	113 ms	2744 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], wh[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)
    {
        out[cur[i]] = true;
        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)
    {
        wh[i] = false;
        if(out[i]) continue;
        move_inside(i);
        czy[i] = true;
        ans = press_button();
        ++xd;
        if(ans > x + 1)
        {
            --xd;
            --ans;
            wh[i] = true;
            czy[i] = false;
            move_outside(i);
        }
    }
    //cerr << "xddd " << x << " " << " " << xd << " " << ans << " " << lft << "\n";
    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(ans == x + 1)
        return ans;

    for(int i = 0; i < n; ++i)
        if(wh[i])
        {
            --lft;
            out[i] = true;
        }
    return ans;
}

int BS(int maks, int n)
{
    int p = 0, 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);
    }
    return p;
}

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

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