Submission #631753

#	Time	Username	Problem	Language	Result	Execution time	Memory
631753		AmirElarbi	Rarest Insects (IOI22_insects)	C++17	0 / 100	182 ms	416 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define ll long long
#define vvi ve<vi>
#define se second
#define fi first
#define pb push_back
 
using namespace std;
const int nax = 2e3+5;
const int MOD = 1e9+7;
 
int pref[nax];
int min_cardinality(int n) {
  int type  = 0;
  for (int i = 0; i < n; ++i)
  {
       move_inside(i);
       int a = press_button();
       if(a == 1)
        type++;
       else 
        move_outside(i);
      pref[i] = type;
  }
  for (int i = 0; i < n; ++i)
  {
    move_outside(i);
  }
  int l = 1,r = n/type+1, ans = 0;
  vi cur, vis(n);
  while(l< r){
    int md = (l+r)/2;
    int nb = 0, nl = l;
    for (int i = 0; i < n; ++i)
    {
        if(vis[i]) {
        	nb++;
        	continue;
        }
        move_inside(i);
        int a = press_button();
        int c  = nb/pref[i];
        if(c*pref[i] == nb){
        	nl = c;
        }
        if(a  > md){
            move_outside(i);
        } else {
            cur.pb(i);
            nb++;
        }
    }
    if(type*md == cur.size()){
        for(auto x : cur) vis[x] = 1;
        l = md+1; ans = md; 
    } else {
        r = md;
        l = nl;
        vi nw;
        for (auto i : cur)
        {
        	if(vis[i]){ 
 						nw.pb(i);
        		continue;
        	}
          move_outside(i);
        }
        cur.clear();
        for(auto x : nw) cur.pb(x);  
    }
  }
  return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     if(type*md == cur.size()){
      |        ~~~~~~~~^~~~~~~~~~~~~

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