Submission #698949

#	Time	Username	Problem	Language	Result	Execution time	Memory
698949		aryan12	Rarest Insects (IOI22_insects)	C++17	53.16 / 100	179 ms	448 KiB

insects

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int min_cardinality(int N) 
{
    int num_insects = 0;
    set<int> s;
    vector<int> order;
    for(int i = 0; i < N; i++)
    {
        order.push_back(i);
    }
    shuffle(order.begin(), order.end(), RNG);
    for(int i = 0; i < N; i++)
    {
        // cout << "moving inside[1]: " << i << endl;
        move_inside(order[i]);
        s.insert(order[i]);
        num_insects++;
        if(press_button() == 2)
        {
            // cout << "moving outside[1]: " << i << endl;
            move_outside(order[i]);
            s.erase(order[i]);
            num_insects--;
        }
    }
    // cout << "num_insects = " << num_insects << endl;
    int l = 2, r = N / num_insects, ans = 1;
    bool flag = true;
    set<int> last_iteration;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        // cout << "mid = " << mid << endl;
        // cout << "s.size() = " << s.size() << endl;
        if(!flag)
        {
            for(auto i: last_iteration)
            {
                // cout << "i = " << i << endl;
                // cout << "moving outside[2]: " << i << endl;
                move_outside(i);
                s.erase(i);
            }
        }
        last_iteration.clear();
        // cout << "hello!" << endl;
        int current_insects = s.size();
        for(int i = 0; i < N; i++)
        {
            if(s.count(order[i])) continue;
            // cout << "moving inside[3]: " << i << endl;
            move_inside(order[i]);
            s.insert(order[i]);
            last_iteration.insert(order[i]);
            current_insects++;
            if(press_button() > mid)
            {
                // cout << "moving outside[3]: " << i << endl;
                move_outside(order[i]);
                s.erase(order[i]);
                last_iteration.erase(order[i]);
                current_insects--;
            }
            if(current_insects == mid * num_insects)
            {
                break;
            }
        }
        // cout << "current_insects = " << current_insects << endl;
        if(current_insects == mid * num_insects)
        {
            ans = mid;
            l = mid + 1;
            flag = true;
        }
        else
        {
            r = mid - 1;
            flag = false;
        }
    }
    return ans;
}

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