Submission #800676

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
800676	2023-08-01 17:59:12	QwertyPi	Rarest Insects (IOI22_insects)	C++17	100 / 100	59 ms	448 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;
bool in[2011]; int sz[2011], mx[2011];
int p[2011];
int cnt = 0;
void move_in(int i){
    i = p[i];
    assert(!in[i]);
    in[i] = true;
    move_inside(i);
    cnt++;
}
void move_out(int i){
    i = p[i];
    assert(in[i]);
    in[i] = false;
    move_outside(i);
    cnt--;
}
int min_cardinality(int N) {
    mt19937 rng(0);
    for(int i = 0; i < N; i++) p[i] = i;
    for(int i = 0; i < N; i++) swap(p[i], p[rng() % (i + 1)]);
    fill(in, in + N, 0);
    fill(sz, sz + N, 0);
    for(int i = 0; i < N; i++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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