Submission #627539

#	Time	Username	Problem	Language	Result	Execution time	Memory
627539		inwbear	Rarest Insects (IOI22_insects)	C++17	57.78 / 100	176 ms	440 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;

int cc[2005],re,rr1,rr2,pos[2005],vi;

int min_cardinality(int N) {
  re=N;
  vector<int>v;
  vector<int>fr;
  for(int i=0;i<N;i++){
    move_inside(i);
    if(press_button()>1){
      move_outside(i);
      fr.pb(i);
    }
    else v.pb(i);
  }
  vi=v.size();
  for(int i=0;i<vi;i++)move_outside(v[i]);
  for(int i=0;(1<<i)<vi;i++){
    rr1=0;
    for(int j=0;j<vi;j++){
      if((j>>i)&(1))move_inside(v[j]),rr1++;
    }
    rr2=vi-rr1-fr.size();
    //printf("%d %d\n",rr1,rr2);
    for(int j=0;j<fr.size();j++){
      move_inside(fr[j]);
      if(press_button()>1)pos[fr[j]]+=(1<<i),rr1--,rr2++;
      move_outside(fr[j]);
    }
    for(int j=0;j<vi;j++){
      if((j>>i)&(1))move_outside(v[j]);
    }
    //printf("%d %d\n",rr1,rr2);
    if(rr1>0||rr2>0)return 1;
  }
  for(int i=0;i<fr.size();i++)cc[v[pos[fr[i]]]]++;
  for(int i=0;i<v.size();i++)re=min(re,cc[v[i]]+1);
  return re;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int j=0;j<fr.size();j++){
      |                 ~^~~~~~~~~~
insects.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<fr.size();i++)cc[v[pos[fr[i]]]]++;
      |               ~^~~~~~~~~~
insects.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=0;i<v.size();i++)re=min(re,cc[v[i]]+1);
      |               ~^~~~~~~~~

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