Submission #926862

#	Time	Username	Problem	Language	Result	Execution time	Memory
926862		beaboss	Rarest Insects (IOI22_insects)	C++17	52.93 / 100	120 ms	1592 KiB

insects

// Source: https://oj.uz/problem/view/IOI22_insects
// 
#include "insects.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

set<int> in, out;

void gout(int i) {
  in.erase(i);
  out.insert(i);
  move_outside(i);
}

void gin(int i) {
  out.erase(i);
  in.insert(i);
  move_inside(i);
}

int min_cardinality(int n) {

  // cout << n << endl;
  FOR(i, 0, n) out.insert(i);

  int d = n;
  FOR(i, 0, n) {
    gin(i);
    if (press_button() > 1) {
      gout(i);
      d--;
    }
  }

  set<int> oth = in;
  for (auto val: oth) {
    gout(val);

  }

  if (d == 1) {
    return n;
  }

  int alr = 0;
  // cout << 'd' << endl;
  int prv = -1;
  int lo  = 1;
  int hi = n / 2;
  while (lo < hi) {
    int t = (lo + hi + 1) / (2);
    prv = out.size();
    // cout << out.size() << t << endl;
    // for (auto val: out) {
    //   cout << val << ' ';
    // }
    // cout << endl;
    // testing t
    set<int> oth = out;
    for (auto val: oth) {
      gin(val);
      if (press_button() > t) {
        gout(val);
      }
    }
    // cout << press_button() << endl;
    if (in.size() == t * d) { // all here --- erase this section
      // alr += t;
      // for (auto it = in.begin(); it != in.end();) {
      //   move_outside(*it);
      //   it++;
      //   in.erase(prev(it, 1));
      // }
      // set<int> oth = in;
      // for (auto val: oth) gout(val);
      lo = t;
    } else { // erase everything not in this section
      out.clear();
      set<int> oth = in;
      for (auto val: oth) gout(val);
      hi = t-1;
    }

  }
  // cout << alr << endl;

  return lo;

}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:85:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |     if (in.size() == t * d) { // all here --- erase this section
      |         ~~~~~~~~~~^~~~~~~~
insects.cpp:63:7: warning: unused variable 'alr' [-Wunused-variable]
   63 |   int alr = 0;
      |       ^~~
insects.cpp:65:7: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
   65 |   int prv = -1;
      |       ^~~

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