Submission #777538

#	Time	Username	Problem	Language	Result	Execution time	Memory
777538		alexander707070	Rarest Insects (IOI22_insects)	C++17	62.81 / 100	134 ms	336 KiB

insects

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

int n,last,cnt,ans,pt;
vector<int> diff,s;
int l[MAXN],r[MAXN],br[MAXN];
bool used[MAXN],in[MAXN];
vector< pair<int,int> > qr;

int lg(int x){
    if(x==1)return 0;
    return lg(x/2)+1;
}

int solve_small(){
    for(int i=1;i<n;i++){
        diff.clear();
 
        for(int i=0;i<n;i++){
            if(used[i])continue;
 
            move_inside(i);
            diff.push_back(i);
 
            if(press_button()>1){
                move_outside(i);
                diff.pop_back();
            }
        }
 
        if(last!=diff.size()){
            return i;
        }
 
        for(int i:diff){
            used[i]=true;
            move_outside(i);
        }
    }
 
    return n;
}

int min_cardinality(int N){
    n=N;

    for(int i=0;i<n;i++){
        move_inside(i);
        diff.push_back(i);

        if(press_button()>1){
            move_outside(i);
            diff.pop_back();
        }
    }

    for(int i:diff){
        used[i]=true; br[i]=1;
        move_outside(i);
    }

    if(diff.size()>n/15){
        last=diff.size();
        return solve_small();
    }

    for(int i=0;i<n;i++){
        if(!used[i]){
            l[i]=-1; r[i]=int(diff.size());
            s.push_back(i);
        }
    }

    for(int i=0;i<lg(int(diff.size()))+1;i++){

        qr.clear();
        for(int f:s){
            qr.push_back({(l[f]+r[f])/2,f});
        }
        sort(qr.begin(),qr.end());

        pt=0;
        for(int f=0;f<qr.size();f++){
            while(pt<=qr[f].first){
                move_inside(diff[pt]); pt++;
            }

            move_inside(qr[f].second);
            in[qr[f].second]=( press_button() == 2 );
            move_outside(qr[f].second);
        }

        for(int f=pt-1;f>=0;f--){
            move_outside(diff[f]);
        }

        for(int f:s){
            if(in[f]){
                r[f]=(l[f]+r[f])/2;
            }else{
                l[f]=(l[f]+r[f])/2;
            }
        }
    }

    for(int i:s){
        br[diff[r[i]]]++;
    }

    ans=n;
    for(int i:diff){
        ans=min(ans,br[i]);
    }

    return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int solve_small()':
insects.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if(last!=diff.size()){
      |            ~~~~^~~~~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     if(diff.size()>n/15){
      |        ~~~~~~~~~~~^~~~~
insects.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int f=0;f<qr.size();f++){
      |                     ~^~~~~~~~~~

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