Submission #632007

#	Time	Username	Problem	Language	Result	Execution time	Memory
632007		typ_ik	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	217 ms	444 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " = " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

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;
  vector<int> cur, vis(n);
  while (l< r) {
    int md = (l+r)/2;
    for (int i = 0; i < n; ++i) {
        if(vis[i]) continue;
        move_inside(i);
        int a = press_button();
        if(a > md){
            move_outside(i);
        } else {
            cur.push_back(i);
        }
    }
    if(type * md == cur.size()){
        for(auto x : cur) vis[x] = 1;
        l = md+1; ans = md;
    } else {
        r = md;
        vector<int> nw;
        for (auto i : cur)
        {
        	if(vis[i]){
                nw.push_back(i);
        		continue;
        	}
          move_outside(i);
        }
        cur.clear();
        for(auto x : nw)
            cur.push_back(x);
    }
  }
  return ans;
}

Compilation message (stderr)

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

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