Submission #1248395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248395		madamadam3	Rarest Insects (IOI22_insects)	C++20	49.97 / 100	41 ms	484 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int) (x).size()

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;

int PUT_IN = 0, TAKE_OUT = 0, PRESS = 0;
vector<int> INDICES;
void put(int i) {
  i = INDICES[i];
  PUT_IN++;
  move_inside(i);
}

void take(int i) {
  i = INDICES[i];
  TAKE_OUT++;
  move_outside(i);
}

int press() {
  PRESS++;
  return press_button();
}

struct DSU {
  int n;
  vi par, siz;

  DSU(int N) {
    n = N;
    par.resize(n); iota(all(par), 0);
    siz.assign(n, 1);
  }

  int find_set(int v) {
    if (par[v] == v) return v;
    return par[v] = find_set(par[v]);
  }

  void union_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);

    if (a != b) {
      if (siz[a] < siz[b]) swap(a, b);
      par[b] = a;
      siz[a] += siz[b];
    }
  }
};

int quadratic(int N) {
  auto dsu = DSU(N);

  FOR(i, 0, N) {
    move_inside(i);
    FOR(j, 0, N) {
      // todo see if I can reduce checks where I already know that there isn't an edge between set a and set b
      if(dsu.find_set(i) == dsu.find_set(j)) continue;
      move_inside(j);
      if (press_button() > 1) {
        dsu.union_set(i, j);
      } 
      move_outside(j);
    }
    move_outside(i);
  }

  int minsz = INT_MAX;
  FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
  return minsz;
}

void window_range(int N, int L, int R, set<int> &active, DSU &dsu) {
  int cursz = 1;

  for (int i = L; i <= R; i++) {
    move_inside(i);
    int newsz = press_button();

    if (newsz > cursz) {
      int toerase = -1;

      for (auto &el : active) {
        move_outside(el);
        if (press_button() < newsz) {
          dsu.union_set(i, el);
          toerase = el;
          break;
        } else {
          move_inside(el);
        }
      }

      if (toerase != -1) active.erase(toerase);
    }

    active.insert(i);
  }

  for (auto &el : active) {
    move_outside(el);
  }
  active.clear();
}

void combine_sets(int N, DSU &dsu, int L1, int R1, int L2, int R2) {
  set<int> p1, p2;
  FOR(i, L1, R1 + 1) {
    p1.insert(dsu.find_set(i));
  }
  FOR(i, L2, R2 + 1) {
    p2.insert(dsu.find_set(i));
  }

  for (auto &el1 : p1) {
    move_inside(el1);
    for (auto &el2 : p2) {
      move_inside(el2);
      if (press_button() > 1) {
        dsu.union_set(el1, el2);
      }
      move_outside(el2);
    }
    move_outside(el1);
  }
}

int window(int N) { // quadratic but faster
  auto dsu = DSU(N);
  set<int> active;

  int L1 = 0, R1 = N / 2, L2 = (N / 2) + 1, R2 = N - 1;

  window_range(N, L1, R1, active, dsu);
  window_range(N, L2, R2, active, dsu);
  combine_sets(N, dsu, L1, R1, L2, R2);

  int minsz = INT_MAX;
  FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
  return minsz;
}



int bsearch(int N) {
  vector<int> reps(1, 0); put(0);
  FOR(i, 1, N) {
    put(i);
    if (press() > 1) {
      take(i);
    } else {
      reps.push_back(i);
    }
  }

  vector<int> cur_in; for (int i = 0; i < sz(reps); i++) take(reps[i]);
  auto dsu = DSU(N);

  for (int i = 0; i < N; i++) {
    if (count(all(reps), i)) continue;
    int lo = 0, hi = sz(reps);

    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      for (int j = 0; j <= mid; j++) {
        cur_in.push_back(reps[j]); put(reps[j]);
      }

      put(i);
      int ans = press(); take(i);
      while (!cur_in.empty()) take(cur_in.back()), cur_in.pop_back();

      if (ans > 1) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }

    dsu.union_set(reps[lo], i);
  }

  int minsz = INT_MAX;
  FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
  return minsz;
}

int bsearch2(int N) {
  vector<int> reps(1, 0); put(0);
  FOR(i, 1, N) {
    put(i);
    if (press() > 1) {
      take(i);
    } else {
      reps.push_back(i);
    }
  }

  vector<int> cur_in; for (int i = 0; i < sz(reps); i++) take(reps[i]);
  auto dsu = DSU(N);

  int mlog = 1; while ((1 << mlog) <= sz(reps)) mlog++;
  vector<int> subs; FOR(i, 0, N) if (!count(all(reps), i)) subs.push_back(i);
  int tsub = sz(subs);
  vector<int> LO(tsub, 0), HI(tsub, sz(reps));

  for (int llg = 0; llg <= mlog; llg++) {
    vector<int> orders; FOR(i, 0, tsub) if (LO[i] < HI[i]) orders.push_back(i);
    sort(all(orders), [&](int a, int b) {int av = (LO[a] + (HI[a] - LO[a]) / 2), bv = (LO[b] + (HI[b] - LO[b]) / 2); return av < bv;;});
    int cmid = -1;
    
    for (int i : orders) {
      int mid = LO[i] + (HI[i] - LO[i]) / 2;

      while (cmid < mid) {
        put(reps[cmid+1]);
        cur_in.push_back(reps[cmid + 1]);
        cmid++;
      }

      // while (cmid > mid) {
      //   take(cur_in.back()); cur_in.pop_back();
      //   cmid--;
      // }

      put(subs[i]); 
      int ans = press(); take(subs[i]);

      if (ans > 1) {
        HI[i] = mid;
      } else {
        LO[i] = mid + 1;
      }
    }
    while (!cur_in.empty()) take(cur_in.back()), cur_in.pop_back();
  }

  for (int i = 0; i < tsub; i++) {
    dsu.union_set(reps[LO[i]], subs[i]);
  }

  int minsz = INT_MAX;
  FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
  return minsz;
}

int min_cardinality(int N) {
  default_random_engine rng;
  INDICES.resize(N); iota(all(INDICES), 0); shuffle(all(INDICES), rng);
  int ans = bsearch2(N);
  // int ans = window(N);
  // cout << "PUT: " << PUT_IN << " TAKE: " << TAKE_OUT << " PRESS: " << PRESS << "\n";
  return ans;
}

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