Submission #805734

#	Time	Username	Problem	Language	Result	Execution time	Memory
805734		caganyanmaz	Rarest Insects (IOI22_insects)	C++17	71.22 / 100	117 ms	444 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
#define pb push_back
#define pp pop_back
using namespace std;

constexpr static int MXSIZE = 2000;
constexpr static int BLOCK = 40;
set<int> b;
int bv[MXSIZE];
int n;



bool check(int count)
{
        vector<int> inserted;
        for (int i = 0; i < n; i++)
        {
                if (b.find(i) != b.end())
                        continue;
                move_inside(i);
                inserted.pb(i);
                if (press_button() > count)
                {
                        inserted.pp();
                        move_outside(i);
                }
        }
        bool res = inserted.size() + b.size() == (b.size() * count);
        for (int i : inserted)
                move_outside(i);
        return res;
}

int find_by_count()
{
        int l = 1, r = 1 + (n / b.size());
        while (r - l > 1)
        {
                int m = l+r>>1;
                if (check(m))
                        l = m;
                else
                        r = m;
        }
        return l;
}


int find_by_element(int l, int r, vector<int> v)
{
        if (r - l == 1)
        {
                move_outside(bv[l]);
                return v.size()+1;
        }
        int m = l+r>>1;
        for (int i = m; i < r; i++)
                move_outside(bv[i]);
        vector<int> lv, rv;
        for (int i : v)
        {
                move_inside(i);
                if (press_button() > 1)
                        lv.pb(i);
                else
                        rv.pb(i);
                move_outside(i);
        }
        int lres = find_by_element(l, m, lv);
        for (int i = m; i < r; i++)
                move_inside(bv[i]);
        int rres = find_by_element(m, r, rv);
        return min(lres, rres);

}

int find_by_element()
{
        int i = 0;
        for (int j : b)
                bv[i++] = j;
        vector<int> v;
        for (int i = 0; i < n; i++)
                if (b.find(i) == b.end())
                        v.pb(i);
        return find_by_element(0, b.size(), v);
}


int min_cardinality(int N)
{
        n = N;
        for (int i = 0; i < n; i++)
        {
                move_inside(i);
                if (press_button() == 1)
                        b.insert(i);
                else
                        move_outside(i);
        }
        if (b.size() > BLOCK)
                return find_by_count();
        else
                return find_by_element();
}

Compilation message (stderr)

insects.cpp: In function 'int find_by_count()':
insects.cpp:41:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |                 int m = l+r>>1;
      |                         ~^~
insects.cpp: In function 'int find_by_element(int, int, std::vector<int>)':
insects.cpp:58:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int m = l+r>>1;
      |                 ~^~

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