Submission #880449

#	Time	Username	Problem	Language	Result	Execution time	Memory
880449		Elvin_Fritl	Rarest Insects (IOI22_insects)	C++17	100 / 100	31 ms	856 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
 
using namespace std;
 
bool color[2001];
 
mt19937_64 rng(time(NULL));

int min_cardinality(int N) {
    move_inside(0);
    color[0] = 1;
 
    int k = 1;
    for (int i = 1; i < N; i++) {
        move_inside(i);
        if(press_button() == 2){
            move_outside(i);
        }
        else{
            color[i] = 1;
            k++;
        }
    }
    vector<int> v;
    for (int i = 0; i < N; i++) {
        v.push_back(i);
    }
  
  	shuffle(v.begin() , v.end() , rng);
    
    int l = 2, r = N / k , ans = 1 , t = k;
    while(l <= r) {
        int mid = (l + r) / 2;
        vector<int> fi , se;
        for (int i : v) {
            if(t == mid * k) {
            	break;
            }
            if(color[i]){
                continue;
            }
            move_inside(i);
            if(press_button() == mid + 1){
                move_outside(i);
                se.push_back(i);
            }
            else{
                color[i] = 1;
                t++;
                fi.push_back(i);
            }
        }
        if(t == mid * k){
            l = mid + 1;
            ans = mid;
        }
        else{
            r = mid - 1;
            for(int i : fi){
                move_outside(i);
                color[i] = 0;
                t--;
            }
            for(int i : se){
                color[i] = 1;
            }
        }
    }
    return ans;
}

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