Submission #628982

#	Time	Username	Problem	Language	Result	Execution time	Memory
628982		Plurm	Rarest Insects (IOI22_insects)	C++17	73.32 / 100	141 ms	496 KiB

insects

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

vector<int> perm;
void mi(int i){
  move_inside(perm[i]);
}
void mo(int i){
  move_outside(perm[i]);
}

int min_cardinality(int N) {
  default_random_engine dre(time(NULL));
  perm.resize(N);
  iota(perm.begin(), perm.end(), 0);
  shuffle(perm.begin(), perm.end(), dre);
  set<int> specials;
  specials.insert(0);
  mi(0);
  for(int i = 1; i < N; i++){
    mi(i);
    if(press_button() == 2){
      mo(i);
    }else{
      specials.insert(i);
    }
  }
  for(int i : specials) mo(i);
  // 2 cases: #t <= sqrt(N) or #t > sqrt(N)
  if(specials.size() * specials.size() <= 1.4 * N){
    // case 1: use N log2 #t approach using pbsearch
    vector<tuple<int,int,int>> pbs;
    int c = -1;
    for(int i = 0; i < N; i++){
      if(specials.count(i) == 0) pbs.push_back({i, 0, c});
      else c++;
    }
    vector<int> svec(specials.begin(), specials.end());
    int ptr = -1;
    while(true){
      bool cont = false;
      for(auto p : pbs){
        if(get<1>(p) != get<2>(p)) cont = true;
      }
      if(!cont) break;
      sort(pbs.begin(), pbs.end(), [](tuple<int,int,int> x, tuple<int,int,int> y){
        return (get<1>(x) + get<2>(x)) / 2 < (get<1>(y) + get<2>(y)) / 2;
      });
      while(ptr > (get<1>(pbs.front()) + get<2>(pbs.front())) / 2){
        mo(svec[ptr]);
        ptr--;
      }
      vector<tuple<int,int,int>> npbs;
      for(auto p : pbs){
        if(get<1>(p) == get<2>(p)){
          npbs.push_back(p);
          continue;
        }
        int mid = (get<1>(p) + get<2>(p)) / 2;
        for(int i = ptr+1; i <= mid; i++) mi(svec[i]);
        ptr = mid;
        mi(get<0>(p));
        if(press_button() == 2){
          // hi = mid
          npbs.push_back({get<0>(p), get<1>(p), mid});
        }else{
          // lo = mid+1
          npbs.push_back({get<0>(p), mid+1, get<2>(p)});
        }
        mo(get<0>(p));
      }
      pbs = npbs;
    }
    map<int,int> cards;
    for(int x : specials) cards[x] = 1;
    for(auto p : pbs) cards[svec[get<1>(p)]]++;
    int mn = 5000;
    for(auto x : cards) mn = min(mn, x.second);
    return mn;
  }else{
    // case 2: use N log2 ans approach using bsearch on ans
    int lo = 1;
    int hi = N / specials.size();
    int mid;
    while(lo < hi){
      mid = (lo + hi)/2;
      set<int> machine;
      for(int i = 0; i < N; i++){
        if(specials.count(i) == 0){
          mi(i);
          machine.insert(i);
          if(press_button() > mid){
            machine.erase(i);
            mo(i);
          }
        }
      }
      bool ok = false;
      vector<int> svec(specials.begin(), specials.end());
      shuffle(svec.begin(), svec.end(), dre);
      for(int x : svec){
        mi(x);
        machine.insert(x);
        if(press_button() == mid){
          ok = true;
          break;
        }
        mo(x);
        machine.erase(x);
      }
      for(int x : machine){
        mo(x);
      }
      if(ok){
        hi = mid;
      }else{
        lo = mid+1;
      }
    }
    return lo;
  }
}

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