#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=0; int CurrentInMachine=0; int PossibleMincount(int cnt){ PrevIndex.clear(); 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(); } } } CurrentInMachine=0; for(int i=0;i<n;i++){ CurrentInMachine+=InMachine[Permutation[i]]; } if(CurrentInMachine!=cnt*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(); return 0; }else if(CurrentInMachine==cnt*TypeCount){ //As every type of insects has at least cnt insects, the answer is at least cnt. Just return true PrevIndex.clear(); for(int i=1;i<=cnt;i++){ ok[i]=1; } return 1; } } int min_cardinality(int 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; } PrevIndex.clear(); int l,r,mid; //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)/2; if(PossibleMincount(mid)){ l=mid; }else{ r=mid-1; } } if(PossibleMincount(r)){ return r; }else{ return l; } }

insects.cpp: In function 'int PossibleMincount(int)':
insects.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^