Submission #636159

#	Time	Username	Problem	Language	Result	Execution time	Memory
636159		slime	Rarest Insects (IOI22_insects)	C++17	99.78 / 100	72 ms	636 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"
using namespace std;

set<int> machine;

int pvans; // Answer doesn't change if machine doesn't change


int inc = 0, outc = 0, qc = 0;
void move_in(int i) {
  if(machine.count(i)) return;
  machine.insert(i);
  move_inside(i);
  inc++;
  pvans = -1;
}

void move_out(int i) {
  if(machine.count(i)) {
    machine.erase(i);
    move_outside(i);
    outc++;
    pvans = -1;
  }
}


int query() {
  if(pvans == -1) {
    qc++;
    return pvans = press_button();
  }
  return pvans;
}


bool in_machine(int i) {
  return machine.count(i);
}
mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int rnd(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}

int min_cardinality(int N) {
  inc = 0, outc = 0, qc = 0;
  machine.clear();
  int T = 0;
  pvans = -1;

  for(int i=0; i<N; i++) {
    move_in(i);
    int pb = query();
    if(pb == 1) {
      T++;
    }
    else {
      move_out(i);
    }
  }

  for(int i=0; i<N; i++) {
    move_out(i);
  }

  if(T == 1) return N;
  int lb = 1, rb = N/T;
  set<int> relevant;
  for(int i=0; i<N; i++) relevant.insert(i);
  int sub = 0;
  while(lb < rb) {
    int mid = (lb + rb + 1) >> 1;
    
    int good = 0;
    int m = relevant.size();

    
    set<int> gv, bv;
    for(int x: relevant) {
      move_in(x);
      
      int qans = query();
      if(qans > mid - sub) {
        move_out(x);
        bv.insert(x);
      }
      else {
        good++;
        gv.insert(x);
      }
    }
    if(good == T * (mid - sub)) {
      lb = mid;
      sub = mid;
      relevant.clear();
      for(int x: bv) relevant.insert(x);

    }
    else {
      rb = mid - 1;
      relevant.clear();
      for(int x: gv) relevant.insert(x);
    }

    for(int i=0; i<N; i++) {
      move_out(i);
    }
  }
  return lb;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:77:9: warning: unused variable 'm' [-Wunused-variable]
   77 |     int m = relevant.size();
      |         ^

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