Submission #636134

#	Time	Username	Problem	Language	Result	Execution time	Memory
636134		slime	Rarest Insects (IOI22_insects)	C++17	90.22 / 100	100 ms	640 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);
  while(lb < rb) {
    int mid = (lb + rb + 1) >> 1;
    
    int overflow = 0;
    int m = relevant.size();
    for(int x: relevant) {
      if(in_machine(x)) continue;
      move_in(x);
      int qans = query();
      if(qans > mid) {
        move_out(x);
        overflow++;

      }
    }
    if(overflow == m - T * mid) {
      lb = mid;
    }
    else {
      rb = mid - 1;
      relevant.clear();

      for(int i=0; i<N; i++) {
        if(in_machine(i)) relevant.insert(i);
        move_out(i);
      }
    }
  }
  return lb;
}

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