Submission #979657

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
979657	2024-05-11 09:32:42	12345678	Rarest Insects (IOI22_insects)	C++17	100 / 100	33 ms	1268 KiB

insects

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=2e3+5;
mt19937 rng(time(0));
int p[nx], cnt, sz, in[nx], t[nx], s[nx];
vector<pair<int, int>> v;
int min_cardinality(int N) {
    cin.tie(NULL)->sync_with_stdio(false);
    for (int i=0; i<N; i++) v.push_back({rng(), i});
    sort(v.begin(), v.end());
    for (int i=0; i<N; i++) p[v[i].second]=i;
    for (int i=0; i<N; i++)
    {
        move_inside(p[i]);
        if (press_button()==1) cnt++, in[i]=1, s[i]=1;
        else move_outside(p[i]);
    }
    if (cnt==1) return N;
    if (cnt==N) return 1;
    int l=1, r=N/cnt;
    sz=cnt;
    while (l<r)
    {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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