Submission #636179

#	Time	Username	Problem	Language	Result	Execution time	Memory
636179		slime	Rarest Insects (IOI22_insects)	C++17	100 / 100	60 ms	568 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;
  vector<int> relevant;
  for(int i=0; i<N; i++) relevant.push_back(i);
  int sub = 0;
  while(lb < rb) {
    int mid = (lb + rb + 1) >> 1;
    
    int good = 0;
    int m = relevant.size();

    shuffle(relevant.begin(), relevant.end(), rng);
 
    
    set<int> gv, bv;
    for(int x: relevant) {
      
      int qans;
      if(mid == sub || good == T * (mid - sub)) qans = 100000;
      else {
        move_in(x);
        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.push_back(x);
    }
    else {
      rb = mid - 1;
      relevant.clear();
      for(int x: gv) relevant.push_back(x);
    }
    if(lb < rb) {
      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:79:9: warning: unused variable 'm' [-Wunused-variable]
   79 |     int m = relevant.size();
      |         ^

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