Submission #628779

#	Time	Username	Problem	Language	Result	Execution time	Memory
628779		toloraia	Rarest Insects (IOI22_insects)	C++17	0 / 100	3080 ms	208 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) < m*2; I++){
        vector < int > v[m];
        bool ok = 1;
        for (int i = 0; i < n; i++){
            if (fix[i] == 0)
                continue;
            if (L[i] == R[i])
                continue;
            ok = 0;
            M[i] = (L[i] + R[i] >> 1);
            v[M[i]].push_back (i);
        }
        if (ok)
            break;
        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);
        }
        for (int x : v)
            move_outside(x);
        if ((int)v.size() < m)
            return ans;
        ans++;
    }
    return ans;
}

int C (int n, int m, vector < int > V){
    vector < bool > fix (n, 1);
    for (int x : V)
        fix[x] = 0;
    V.clear();
    for (int i = 0; i < n; i++)
        if (fix[i])
            V.push_back (i);
    int l = 1, r = n/m;
    //cout << l << " " << r << endl;
    while (l < r){
        int mid = l + r + 1 >> 1;
        vector < int > v;
        for (int i : V){
            move_inside(i);
            if (press_button() < mid){
                v.push_back(i);
            }
            else
                move_outside(i);
        }
        for (int x : v)
            move_outside(x);
        if ((int)v.size() == m*(mid-1))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

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 *= n;
    int ans2 = 0;
    while ((1 << ans1) < n/m)
        ans2++;
    ans2 *= n-m;
    //cout << ans1 << " " << ans2 << endl;
    if (ans1 < ans2)
        return A(n, V);

    return C(n, m, V);
}

Compilation message (stderr)

insects.cpp: In function 'int A(int, std::vector<int>)':
insects.cpp:22:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             M[i] = (L[i] + R[i] >> 1);
insects.cpp: In function 'int C(int, int, std::vector<int>)':
insects.cpp:94:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid = l + r + 1 >> 1;
      |                   ~~~~~~^~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:126:9: warning: unused variable 'k' [-Wunused-variable]
  126 |     int k = n - m;
      |         ^

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