Submission #797395

#	Time	Username	Problem	Language	Result	Execution time	Memory
797395		penguinman	Rarest Insects (IOI22_insects)	C++17	25 / 100	206 ms	468 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

constexpr ll mod = 1'000'002'022;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define ln "\n"


struct union_find{
  int N;
  vi par;
  union_find(int n): N(n){
    par.resize(N);
    rep(i,0,N) par[i] = i;
  }
  ll root(ll u){
    if(par[u] == u) return u;
    return par[u] = root(par[u]);
  }
  void merge(ll u, ll v){
    u = root(u);
    v = root(v);
    if(u != v){
      par[u] = v;
    }
  }
};

int min_cardinality(int N) {
  union_find tree(N);
  auto merge = [&](vi L, vi R){
    std::set<ll> nex;
    {
      vi nL, nR;
      rep(i,0,L.size()) move_inside(L[i]);
      rep(i,0,R.size()){
        move_inside(R[i]);
        if(press_button() == 1){
          nex.insert(R[i]);
        }
        else{
          nR.pb(R[i]);
        }
        move_outside(R[i]);
      }
      rep(i,0,L.size()) move_outside(L[i]);
      rep(i,0,R.size()) move_inside(R[i]);
      rep(i,0,L.size()){
        move_inside(L[i]);
        if(press_button() == 1){
          nex.insert(L[i]);
        }
        else{
          nL.pb(L[i]);
        }
        move_outside(L[i]);
      }
      rep(i,0,R.size()) move_outside(R[i]);
      L = nL;
      R = nR;
      assert(L.size() == R.size());
    }
    if(L.size() > R.size()) std::swap(L,R);
    ll sz = R.size();
    vi flag(sz);
    rep(i,0,sz){
      move_inside(L[i]);
      rep(j,0,sz){
        if(flag[j]) continue;
        move_inside(R[j]);
        if(press_button() == 2){
          flag[j] = true;
          tree.merge(L[i], R[j]);
          move_outside(R[j]);
          break;
        }
        move_outside(R[j]);
      }
      move_outside(L[i]);
    }
    for(auto el: L) nex.insert(el);
    vi ret(all(nex));
    /*cout << l << " " << r << "  ";
    for(auto el: L) cout << el << " ";
    cout << " ";
    for(auto el: R) cout << el  << " ";
    cout << " ";
    rep(i,0,sz) cout << left[i] << " ";
    cout << " ";
    for(auto el: ret) cout << el << " ";
    cout << endl;*/
    return ret;
  };
  vii data(N);
  rep(i,0,N) data[i] = {i};
  rep(_,1,N){
    ll len = data.size();
    rep(i,0,len){
      if(data[len-1].size() > data[i].size()) std::swap(data[len-1], data[i]);
    }
    rep(i,0,len-1){
      if(data[len-2].size() > data[i].size()) std::swap(data[len-2], data[i]);
    }
    vi next = merge(data[len-2], data[len-1]);
    data[len-2] = next;
    data.pop_back();
  }
  vi cnt(N);
  //rep(i,0,N) cout << tree.root(i) << endl;
  rep(i,0,N) cnt[tree.root(i)]++;
  ll min = N;
  rep(i,0,N){
    if(cnt[i]) min = std::min(min, cnt[i]);
  }
  return int(min);
}

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