Submission #639164

#	Time	Username	Problem	Language	Result	Execution time	Memory
639164		Blagojce	Rarest Insects (IOI22_insects)	C++17	47.51 / 100	218 ms	540 KiB

insects

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <string.h>
#include <bitset>
#include <numeric>
#include <utility>
#include <random>
#include <cassert>
 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
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);
        }
    }
}

bool histogram(int h){
    int area = Unique.size();
    
    vector<int> v;
    fr(i, 0, n){
        if(dont_use[i]) continue;
        move_inside(i);
        int cnt = press_button();
        if(cnt > h){
            move_outside(i);
        }
        else{
            ++area;
            v.pb(i);
        }
    }
    for(auto i : v){
        move_outside(i);
    }
    
    return area == h * Unique.size();
}

int min_cardinality(int N) {
    n = N;
    find_unique();
    int l = 1, r = N;
    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:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     return area == h * Unique.size();
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~

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