Submission #730363

#	Time	Username	Problem	Language	Result	Execution time	Memory
730363		caganyanmaz	Rarest Insects (IOI22_insects)	C++17	25 / 100	84 ms	356 KiB

insects

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

void move_inside(int i);
void move_outside(int i);
int press_button();

int brute(const vector<int>& basis, int n)
{
        set<int> selected;
        for (int i : basis)
        {
                selected.insert(i);
                move_outside(i);
        }
        int count = 1;
        while (true)
        {
                vector<int> next_basis;
                for (int i = 0; i < n; i++)
                {
                        if (selected.find(i) == selected.end())
                        {
                                move_inside(i);
                                if (press_button() > 1)
                                        move_outside(i);
                                else
                                        next_basis.pb(i);
                        }
                }
                if (next_basis.size() != basis.size())
                        return count;
                count++;
                for (int i : next_basis)
                        selected.insert(i);
        }
}

int find(const vector<int>& basis, int l, int r, const vector<int>& permutation)
{
        if (r - l == 1)
                return permutation.size() + 1;
        int m = l+r>>1;
        for (int i = m; i < r; i++)
                move_outside(basis[i]);
        vector<int> lp, rp;
        for (int i : permutation)
        {
                move_inside(i);
                if (press_button() == 1)
                        rp.pb(i);
                else
                        lp.pb(i);
                move_outside(i);
        }
        int lr = find(basis, l, m, lp);
        for (int i = 0; i < m; i++)
                move_outside(basis[i]);
        for (int i = m; i < r; i++)
                move_inside(basis[i]);
        int rr = find(basis, m, r, rp);
        return min(lr, rr);
}

int min_cardinality(int n)
{
        vector<int> basis;
        for (int i = 0; i < n; i++)
        {
                move_inside(i);
                if (press_button() != 1)
                        move_outside(i);
                else
                        basis.pb(i);
        }
        if (basis.size() * 6 >= n)
                return brute(basis, n);
        vector<int> permutation;
        for (int i = 0; i < n; i++)
                if (*lower_bound(basis.begin(), basis.end(), i) != i)
                        permutation.pb(i);
        return find(basis, 0, basis.size(), permutation);
}

Compilation message (stderr)

insects.cpp: In function 'int find(const std::vector<int>&, int, int, const std::vector<int>&)':
insects.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int m = l+r>>1;
      |                 ~^~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:77:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |         if (basis.size() * 6 >= n)
      |             ~~~~~~~~~~~~~~~~~^~~~

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