oj.uz

Submission #942182

# Submission time Handle Problem Language Result Execution time Memory
942182 2024-03-10T10:34:56 Z benjaminkleyn Rarest Insects (IOI22_insects) C++17
0 / 100
 33 ms 848 KB 
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;

int cnt;
bool inside[2000];
bool bad[2000];

void init()
{
    cnt = 0;
    memset(inside, false, sizeof(inside));
    memset(bad, false, sizeof(bad));
}
void move_in(int i)
{
    if (inside[i])
        return;
    cnt++;
    inside[i] = true;
    move_inside(i);
}
void move_out(int i)
{
    if (!inside[i])
        return;
    cnt--;
    inside[i] = false;
    move_outside(i);
}

int min_cardinality(int N) 
{
    init();
    for (int i = 0; i < N; i++)
    {
        move_in(i);
        if (press_button() > 1)
            move_out(i);
    }
    int num_types = cnt;

    if (num_types == 1)
        return N;
    if (num_types == N)
        return 1;

    int lo = 1, hi = N / cnt + 1, mid, ans = 1;
    while (lo < hi)
    {
        mid = (lo + hi + 1)/ 2;

        vector<int> new_insects;
        vector<int> bad_insects;
        for (int i = 0; i < N; i++)
        {
            if (!(bad[i] || inside[i]))
            {
                move_in(i);

                if (press_button() > mid)
                {
                    bad_insects.push_back(i);
                    move_out(i);
                }
                else
                    new_insects.push_back(i);

                if (cnt >= mid * num_types)
                    break;
            }
        }

        if (cnt == mid * num_types)
            ans = mid, lo = mid + 1;
        else
        {
            for (int i : bad_insects)
                bad[i] = true;
            for (int i : new_insects)
                move_out(i);
            hi = mid - 1;
        }
    }
    return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 596 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 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Incorrect 2 ms 600 KB Wrong answer.
10 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 1 ms 344 KB Output is correct
3 Correct 0 ms 596 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 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Incorrect 2 ms 600 KB Wrong answer.
10 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 Correct 0 ms 344 KB Output is correct
7 Correct 10 ms 344 KB Output is correct
8 Correct 10 ms 596 KB Output is correct
9 Correct 19 ms 432 KB Output is correct
10 Correct 30 ms 428 KB Output is correct
11 Correct 33 ms 592 KB Output is correct
12 Correct 14 ms 848 KB Output is correct
13 Correct 33 ms 668 KB Output is correct
14 Correct 31 ms 600 KB Output is correct
15 Correct 23 ms 596 KB Output is correct
16 Incorrect 21 ms 424 KB Wrong answer.
17 Halted 0 ms 0 KB -