Submission #689839

#	Time	Username	Problem	Language	Result	Execution time	Memory
689839		NemanjaSo2005	Rarest Insects (IOI22_insects)	C++17	96.85 / 100	69 ms	448 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,niz[2005];
mt19937_64 rng;
int sp;
vector<int> V,tmp;
bool moguce(int kol){
   for(int i=0;i<V.size();i++){
      if(tmp.size()==kol*sp)
         break;
      move_inside(V[i]);
      if(press_button()==kol+1){
         move_outside(V[i]);
         continue;
      }
      tmp.push_back(V[i]);
      swap(V[i],V[V.size()-1]);
      V.pop_back();
      i--;
   }
   for(int i=0;i<tmp.size();i++)
      move_outside(tmp[i]);
   if(sp==-1)
      sp=tmp.size();
   if(tmp.size()==kol*sp){
      tmp.clear();
      return true;
   }
   V=tmp;
   tmp.clear();
   return false;
}
int min_cardinality(int n){
   rng.seed(6333);
   N=n;
   for(int i=1;i<=N;i++)
      niz[i]=i-1;
   //for(int i=1;i<=5*N;i++)
    //  swap(niz[rng()%N+1],niz[rng()%N+1]);
   tmp.clear();
   for(int i=1;i<=N;i++)
      V.push_back(niz[i]);
   sp=-1;
   moguce(1);
   int br=1;
   int maks=V.size()/sp;
   int K=1;
   while(K<=maks)
      K*=2;
   K/=2;
   while(K){
      if(moguce(K))
         br+=K;
      K/=2;
   }
   return br;
}

Compilation message (stderr)

insects.cpp: In function 'bool moguce(int)':
insects.cpp:10:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
insects.cpp:11:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |       if(tmp.size()==kol*sp)
      |          ~~~~~~~~~~^~~~~~~~
insects.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    for(int i=0;i<tmp.size();i++)
      |                ~^~~~~~~~~~~
insects.cpp:27:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |    if(tmp.size()==kol*sp){
      |       ~~~~~~~~~~^~~~~~~~

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