Submission #797743

#	Time	Username	Problem	Language	Result	Execution time	Memory
797743		HaroldVemeno	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	208 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int min_cardinality(int n) {
    vector<bool> skip(n);
    vector<bool> box(n);
    int s = 0;
    for(int i = 0; i < n; ++i) {
        box[i] = true;
        move_inside(i);
        ++s;
        int c = press_button();
        if(c > 1) {
            move_outside(i);
            --s;
            box[i] = false;
        }
    }
    if(s == n) return 1;
    for(int i = 0; i < n; ++i) {
        if(box[i]) {
            move_outside(i);
            skip[i] = true;
        }
    }
    int rm = 1;
    int f = 1;
    int t = n/s;
    while(f != t) {
        int m = (f+t+1)/2;
        for(int i = 0; i < n; ++i) {
            if(skip[i]) continue;
            box[i] = true;
            move_inside(i);
            int c = press_button();
            if(c > m-rm) {
                move_outside(i);
                --s;
                box[i] = false;
            }
        }
        if(box.size() == s*(m-rm)) {
            rm = m;
            f = m;
            for(int i = 0; i < n; ++i) {
                if(box[i]) skip[i] = true;
            }
        } else {
            t = m-1;
            for(int i = 0; i < n; ++i) {
                if(!box[i]) skip[i] = true;
            }
        }
        for(int i = 0; i < n; ++i) {
            if(box[i]) move_outside(i);
            box[i] = false;
        }
    }
    return f;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:57:23: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |         if(box.size() == s*(m-rm)) {
      |            ~~~~~~~~~~~^~~~~~~~~~~

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