Submission #639169

#	Time	Username	Problem	Language	Result	Execution time	Memory
639169		Blagojce	Rarest Insects (IOI22_insects)	C++17	Compilation error	0 ms	0 KiB

insects

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <cassert>
 
#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:42:1: error: 'mt19937' does not name a type
   42 | mt19937 _rand(time(NULL));
      | ^~~~~~~
insects.cpp: In function 'bool histogram(int)':
insects.cpp:45:37: error: '_rand' was not declared in this scope; did you mean 'srand'?
   45 |     shuffle(ids.begin(), ids.end(), _rand);
      |                                     ^~~~~
      |                                     srand
insects.cpp:63:17: 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()) break;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
insects.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     if(area == h * Unique.size()){
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~
insects.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     return area == h * Unique.size();
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~