Submission #630407

#	Time	Username	Problem	Language	Result	Execution time	Memory
630407		talant117408	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	231 ms	476 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "stub.cpp"
#endif

using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
#define PI                  2*acos(0.0)

int min_cardinality(int n) {
    int different = 1;
    vector <int> inside;
    move_inside(0);
    inside.pb(0);
    for (int i = 1; i < n; i++) {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
        }
        else {
            different++;
            inside.pb(i);
        }
    }
    for (auto x : inside) {
        move_outside(x);
    }
    
    int l = 2, r = n + 1;
    
    while (l < r) {
        int mid = (l + r) >> 1;
        inside.clear();
        for (int i = 0; i < n; i++) {
            move_inside(i);
            if (press_button() > mid) {
                move_outside(i);
            }
            else {
                inside.pb(i);
            }
        }
        if (sz(inside) != different * mid) {
            r = mid;
            for (auto x : inside) {
                move_outside(x);
            }
        }
        else {
            l = mid + 1;
        }
    }
    return l - 1;
}

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