Submission #763450

#	Time	Username	Problem	Language	Result	Execution time	Memory
763450		ZeroCool	Rarest Insects (IOI22_insects)	C++17	100 / 100	48 ms	324 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define ll long long
#define inf 1e9

using namespace std;



bool good[2001];
int Unique(int n){
    int cnt = 0 ;
    for(int i = 0;i<n;i++){
        move_inside(i);

        if(press_button() == 2){
            move_outside(i);
            continue;
        }
        cnt++;
        good[i] = false;
    }
    return cnt;
}

mt19937 _rand(time(NULL));

int min_cardinality(int n) {
    vector<int> v;
    for(int i = 0;i<n;i++){
        v.push_back(i);
        good[i] = true;
    }

    int unique = Unique(n);

    int l = 1;
    int r = (n / unique) + 1;
    int placed = unique;

    while(l + 1 < r){
        shuffle(v.begin(),v.end(),_rand);
        int mid = (l+r)/2;
        int area = placed;

        queue<int> bad;
        queue<int> used;

        for(auto i : v){
            if(area == unique * mid)break;
            if(good[i]){
                move_inside(i);
                if(press_button() > mid){
                    bad.push(i);
                    move_outside(i);
                }else{
                    used.push(i);
                    area++;
                }
            }
        }

        if(area == unique * mid){
            while(!used.empty()){
                good[used.front()] = false;
                used.pop();
            }
            placed = area;
            l = mid;
        }else{
            while(!bad.empty()){
                good[bad.front()] = false;
                bad.pop();
            }
            while(!used.empty()){
                move_outside(used.front());
                used.pop();
            }
            r = mid;
        }
    }
    return l;

    
}

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