Submission #639171

#	Time	Username	Problem	Language	Result	Execution time	Memory
639171		Blagojce	Rarest Insects (IOI22_insects)	C++17	100 / 100	58 ms	432 KiB

insects

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
 
using namespace std;
const int mxn = 2e3;


#include "insects.h"

int n;
vector<int> Unique;

bool dont_use[mxn];

void restrict_this(int x){
    dont_use[x] = true;
}

void find_unique(){
    fr(i, 0, n){
        move_inside(i);
        int cnt = press_button();
        if(cnt == 2){
            move_outside(i);
        }
        else{
            restrict_this(i);
            Unique.pb(i);
        }
    }
}
int add = 0;
vector<int> ids;

mt19937 _rand(time(NULL));

bool histogram(int h){
    shuffle(ids.begin(), ids.end(), _rand);
    
    int area = Unique.size() + add;
    
    vector<int> good;
    vector<int> bad;
    for(auto i : ids){
        if(dont_use[i]) continue;
        move_inside(i);
        int cnt = press_button();
        if(cnt > h){
            bad.pb(i);
            move_outside(i);
        }
        else{
            ++area;
            good.pb(i);
        }
        if(area == h * Unique.size()) break;
    }
    if(area == h * Unique.size()){
        add += (int)good.size();
        for(auto i : good){
            restrict_this(i);
        }
    }
    else{
        for(auto i : bad){
            restrict_this(i);
        }
        for(auto i : good){
            move_outside(i);
        }
    }
    return area == h * Unique.size();
}

int min_cardinality(int N) {
    n = N;
    fr(i, 0, N) ids.pb(i);
    
    
    find_unique();
    int l = 1, r = N/Unique.size();
    while(l < r){
        int m = (l + r + 1)/2;
        if(histogram(m)){
            l = m;
        }
        else{
            r = m-1;
        }
    }
    return l;
}

Compilation message (stderr)

insects.cpp: In function 'bool histogram(int)':
insects.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if(area == h * Unique.size()) break;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
insects.cpp:63:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if(area == h * Unique.size()){
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~
insects.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     return area == h * Unique.size();
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~

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