Submission #630417

#	Time	Username	Problem	Language	Result	Execution time	Memory
630417		talant117408	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 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;
    for (int i = 0; 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 = 1, r = n + 1;
    vector <int> used(n);
    set <int> in_box;
    
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        inside.clear();
        for (int i = 0; i < n; i++) {
            if (used[i] == 1) {
                continue;
            }
            if (sz(in_box) == different * mid) {
                continue;
            }
            move_inside(i);
            if (press_button() > mid) {
                move_outside(i);
            }
            else {
                in_box.insert(i);
                inside.pb(i);
                used[i] = 1;
            }
        }
        if (sz(in_box) == different * mid) {
            l = mid;
        }
        else {
            r = mid;
            for (auto to : inside) {
                move_outside(to);
                used[to] = 0;
                in_box.erase(to);
            }
        }
    }
    
    return l;
}

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