제출 #1211473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211473		mychecksedad	드문 곤충 (IOI22_insects)	C++17	99.76 / 100	15 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define en cout << '\n'
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
const int N = 1e5+10;


int last_pres = 0;
int press_buttoon(){
  return last_pres = press_button();
}

int min_cardinality(int n) {
  vi v, u;
  for(int i = 0; i < n; ++i){
    move_inside(i);
    int val = press_button();
    if(val > 1){
      move_outside(i);
      u.pb(i);
    }else{
      v.pb(i);
    }
    // u.pb(i);
  }
  // for(int x: v) move_outside(x);
  int sz = v.size();
  // v.clear();

  last_pres = 1;

  int l = 1, r = n / sz, ans = r;
  int inside = sz;
  while(l <= r){
    int mid = l+r>>1;
    // u is the cur search set, v is the inside set.

    if(last_pres <= mid){
      // we gotta add new ones from u.
      // the ones in v are fixed.
      v.clear();
      vi U;
      for(int x: u){
        move_inside(x);
        if(press_buttoon() <= mid){
          v.pb(x);
          ++inside;
        }else{
          move_outside(x);
          U.pb(x);
        }
      }
      u = U;
    }else{
      // we gotta erase some from v.
      u.clear();
      for(int x: v) move_outside(x), --inside;
      vi V;
      for(int x: v){
        move_inside(x);
        if(press_buttoon() <= mid){
          V.pb(x);
          ++inside;
        }else{
          u.pb(x);
          move_outside(x);
        }
      }
      v = V;
    }
    // cerr << l << ' ' << r << " :\n";
    // for(int x: v) cerr << x << ' ';  cerr << '\n';
    // for(int x: u) cerr << x << ' ';  cerr << '\n';
    // cerr << '\n';
    if(inside == mid * sz){
      ans = mid;
      l = mid + 1;
    }else{
      r = mid - 1;
    }

  }

  return ans;
}

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