oj.uz

Submission #967949

# Submission time Handle Problem Language Result Execution time Memory
967949 2024-04-23T05:58:33 Z 12345678 Rarest Insects (IOI22_insects) C++17
0 / 100
 46 ms 1424 KB 
#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;

int p, cnt, sz, in[nx], t[nx], s[nx];

int min_cardinality(int N) {
    cin.tie(NULL)->sync_with_stdio(false);
    for (int i=0; i<N; i++)
    {
        move_inside(i);
        if (press_button()==1) cnt++, in[i]=1, s[i]=1;
        else move_outside(i);
    }
    if (cnt==1) return N;
    if (cnt==N) return 1;
    int l=1, r=N/cnt;
    sz=cnt;
    while (l<r)
    {
        int md=(l+r+1)/2;
        for (int i=0; i<N; i++)
        {
            if (s[i]||t[i]) continue;
            move_inside(i);
            if (press_button()>md) move_outside(i);
            else sz++, in[i]=1;
        }
        if (sz==cnt*md) 
        {
            l=md;
            for (int i=0; i<N; i++) if (in[i]) s[i]=1;
        }
        else 
        {
            r=md-1;
            for (int i=0; i<N; i++) if (!in[i]) t[i]=1;
            for (int i=0; i<N; i++) if (!s[i]) move_outside(i), sz--;
        }
    }
    return l;
}

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 1 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 468 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 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 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 468 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 12 ms 344 KB Output is correct
8 Correct 12 ms 600 KB Output is correct
9 Correct 22 ms 592 KB Output is correct
10 Partially correct 33 ms 700 KB Output is partially correct
11 Partially correct 42 ms 1152 KB Output is partially correct
12 Correct 11 ms 592 KB Output is correct
13 Incorrect 46 ms 1424 KB Wrong answer.
14 Halted 0 ms 0 KB -