oj.uz

Submission #1061962

# Submission time Handle Problem Language Result Execution time Memory
1061962 2024-08-16T16:04:29 Z jerzyk Rarest Insects (IOI22_insects) C++17
0 / 100
 8 ms 600 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Incorrect 8 ms 600 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Incorrect 8 ms 600 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Wrong answer.
7 Halted 0 ms 0 KB -