Submission #1185620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185620		PagodePaiva	Rarest Insects (IOI22_insects)	C++20	61.05 / 100	40 ms	544 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 2010;
int cnt[N];
vector <int> rep;
set <int> simulate;

void moveinside(int pos){
    if(simulate.find(pos) != simulate.end())
        return;
    simulate.insert(pos);
    move_inside(pos);
}
                                                                                                                            
void moveoutside(int pos){
    if(simulate.find(pos) == simulate.end())
        return;
    simulate.erase(pos);
    move_outside(pos);
}

void solve(int l, int r, vector <int> ask){
    if(l == r){
        cnt[rep[l]] = ask.size()+1;
        return;
    }
    vector <int> v1, v2;
    int mid = (l+r)/2;
    for(int i = l;i <= mid;i++){
        moveinside(rep[i]);
    }
    for(int i = mid+1;i <= r;i++){
        moveoutside(rep[i]);
    }
    for(auto x : ask){
        moveinside(x);
        int val = press_button();
        moveoutside(x);
        if(val > 1) v1.push_back(x);
        else v2.push_back(x);
    }
    if(v1.size() < v2.size()){
        solve(l, mid, v1);
        solve(mid+1, r, v2);
    }
    else{
        solve(mid+1, r, v2);
        solve(l, mid, v1);
    }
    return;
}

int min_cardinality(int n) {
    srand(time(0));
    rep.push_back(0);
    moveinside(0);
    vector <int> at;
    for(int i = 1;i < n;i++){
        moveinside(i);
        int v = press_button();
        if(v > 1) {
            moveoutside(i);
            at.push_back(i);
        }
        else{
            rep.push_back(i);
        }
    }
    random_shuffle(rep.begin(), rep.end());
    solve(0, rep.size()-1,at);
    int ans = 1e9;
    for(auto x : rep){
        //cout << cnt[x] << ' ';
        ans = min(ans, cnt[x]);
    }
    return ans;
}

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