Submission #636105

#	Time	Username	Problem	Language	Result	Execution time	Memory
636105		slime	Rarest Insects (IOI22_insects)	C++17	0 / 100	64 ms	548 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

void move_in(int i) {
  if(machine.count(i)) return;
  machine.insert(i);
  move_inside(i);
  pvans = -1;
}

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


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


bool in_machine(int i) {
  return machine.count(i);
}

int min_cardinality(int N) {
  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);
  }
  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 m = relevant.size();
    int overflow = 0;
    for(int x: relevant) {
      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);
      }
    }
  }
  return lb;
}

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