#include <bits/stdc++.h> #include "insects.h" //#include "stub.cpp" using namespace std; deque <int> PrevIndex; int InMachine[2003]; int Permutation[2003]; //saving the answer of each iteration so that we won't accidentially binsearch something we've already calculated int ok[2003]; int n; int TypeCount; int CurrentInMachine; int l,r,mid; int PossibleMincount(int cnt){ while(!PrevIndex.empty()){ PrevIndex.pop_back(); } if(ok[cnt]){ return 1; } //Pushing insects inside the machine, keeping track of the ones being putted inside for this iteration of binary searching for(int i=0;i<n;i++){ if(!InMachine[Permutation[i]]){ InMachine[Permutation[i]]=1; move_inside(Permutation[i]); PrevIndex.push_back(Permutation[i]); if(press_button()>cnt){ move_outside(Permutation[i]); InMachine[Permutation[i]]=0; PrevIndex.pop_back(); } if(PrevIndex.size()==(cnt-l)*TypeCount){ break; } } } if(PrevIndex.size()!=(cnt-l)*TypeCount){ //There clearly exist a type of insect with cardinality less than cnt, so the answer is less than cnt. Removing insects from last iteration. while(!PrevIndex.empty()){ InMachine[PrevIndex.front()]=0; move_outside(PrevIndex.front()); PrevIndex.pop_front(); } PrevIndex.clear();\ CurrentInMachine=0; for(int i=0;i<n;i++){ CurrentInMachine+=InMachine[Permutation[i]]; } return 0; }else{ //As every type of insects has at least cnt insects, the answer is at least cnt. Just return true while(!PrevIndex.empty()){ PrevIndex.pop_back(); } CurrentInMachine=0; for(int i=0;i<n;i++){ CurrentInMachine+=InMachine[Permutation[i]]; } return 1; } } int min_cardinality(int N){ n=N; //Create a random permutation to fuck with shitty tests and achieve better query efficiency for(int i=0;i<N;i++){ Permutation[i]=i; } srand(time(NULL)); int Tempval; for(int i=N-1;i>0;i--){ Tempval=rand()%i; swap(Permutation[i],Permutation[Tempval]); } //Remember to initialize as this is multitest for(int i=0;i<N;i++){ InMachine[Permutation[i]]=0; ok[i+1]=0; } while(!PrevIndex.empty()){ PrevIndex.pop_back(); } //Phase 1: Determining the amount of different types of insects for(int i=0;i<n;i++){ move_inside(Permutation[i]); InMachine[Permutation[i]]=1; PrevIndex.push_back(Permutation[i]); if(press_button()>1){ move_outside(Permutation[i]); InMachine[Permutation[i]]=0; PrevIndex.pop_back(); } } TypeCount=PrevIndex.size(); r=(N/TypeCount); l=1; //Phase 2: Binary search for the answer while(r-l>=1){ mid=(l+r+1)/2; if(PossibleMincount(mid)){ l=mid; r=mid+(N-CurrentInMachine)/TypeCount+1; }else{ r=mid-1; } } if(ok[r]){ return r; }else{ return l; } }

insects.cpp: In function 'int PossibleMincount(int)':
insects.cpp:34:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |    if(PrevIndex.size()==(cnt-l)*TypeCount){
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
insects.cpp:39:21: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  if(PrevIndex.size()!=(cnt-l)*TypeCount){
      |     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~