Submission #628686

#	Time	Username	Problem	Language	Result	Execution time	Memory
628686		toloraia	Rarest Insects (IOI22_insects)	C++17	20.45 / 100	308 ms	468 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int A (int n, vector < int > V){
    vector < bool > fix (n, 1);
    for (int x : V)
        fix[x] = 0;
    int m = (int)V.size();
    vector < int > L(n, 0);
    vector < int > R(n, m-1);
    vector < int > M(n);
    for (int I = 0; (1 << I) < n*2; I++){
        vector < int > v[m];
        for (int i = 0; i < n; i++){
            if (fix[i] == 0)
                continue;
            M[i] = (L[i] + R[i] >> 1);
            v[M[i]].push_back (i);
        }
        for (int i = 0; i < m; i++){
            move_inside(V[i]);
            for (int x : v[i]){
                move_inside(x);
                if (press_button() == 1)
                    L[x] = M[x] + 1;
                else
                    R[x] = M[x];
                move_outside(x);
            }
        }
        for (int x : V)
            move_outside(x);
    }
    vector < int > cnt (m, 1);
    for (int i = 0; i < n; i++)
        if (fix[i])
            cnt[L[i]]++;
    int ans = cnt[0];
    for (int i = 1; i < m; i++)
        ans = min (ans, cnt[i]);
    return ans;
}

int B (int n, vector < int > V){
    vector < bool > fix (n, 1);
    for (int x : V)
        fix[x] = 0;
    int ans = 1;
    int m = (int)V.size();
    while (1){
        V.clear();
        for (int i = 0; i < n; i++)
            if (fix[i])
                V.push_back(i);
        if ((int)V.size() < m)
            return ans;
        vector < int > v;
        for (int x : V){
            move_inside(x);
            if (press_button() == 1){
                v.push_back(x);
                fix[x] = 0;
            }
            else
                move_outside(x);
        }
        if ((int)v.size() < m)
            return ans;
        ans++;
    }
    return ans;
}

int min_cardinality(int n) {
    vector < int > V;
    for (int i = 0; i < n; i++){
        move_inside(i);
        if (press_button() == 1)
            V.push_back(i);
        else
            move_outside(i);
    }
    for (int x : V)
        move_outside(x);
    int m = (int)V.size();
    int k = n - m;
    int ans1 = 0;
    while ((1 << ans1) < m)
        ans1++;
    ans1 *= k;
    int ans2 = 0;
    while (k >= m){
        ans2 += k;
        k -= m;
    }
    if (ans1 < ans2)
        return A(n, V);
    return B(n, V);
}

Compilation message (stderr)

insects.cpp: In function 'int A(int, std::vector<int>)':
insects.cpp:18:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |             M[i] = (L[i] + R[i] >> 1);

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