Submission #718915

#	Time	Username	Problem	Language	Result	Execution time	Memory
718915		baojiaopisu	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	64 ms	412 KiB

insects

#include "insects.h"

#include <cassert>
#include <cstdio>

#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define pb push_back

int min_cardinality(int n) {
  vector<int> curr, q;
  for(int i = 0; i < n; i++) {
    move_inside(i);
    int x = press_button();
    if(x > 1) move_outside(i), q.pb(i);
    else curr.pb(i);
  }

  int num = curr.size();
  int l = 2, r = n / curr.size();
  
  int d = 1, ans = 1; 
  while(l <= r) {
    int mid = (l + r) >> 1;
    vector<int> nxt_q;
    vector<int> cc = curr;
    vector<int> t;

    int cnt = 0;
    for(int i = 0; i < q.size(); i++) {
      move_inside(q[i]);
      int x = press_button();
      if(x > mid) move_outside(q[i]), nxt_q.pb(q[i]);
      else curr.pb(q[i]), t.pb(q[i]), ++cnt;
    }

    if(cnt == (mid - d) * num) {
      d = mid;
      curr.clear();
      q = nxt_q;
      ans = mid;
      l = mid + 1;
    } else {
      for(auto x : t) move_outside(x);
      curr = cc;
      q = t;
      r = mid - 1;
    }
  }

  return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0; i < q.size(); i++) {
      |                    ~~^~~~~~~~~~

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