Submission #1079998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079998		LittleOrange	Rarest Insects (IOI22_insects)	C++17	25 / 100	231 ms	596 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct dsu{
  vector<ll> p;
  dsu(ll n):p(n,-1){}
  ll g(ll i){
    return p[i]<0?i:p[i] = g(p[i]);
  }
  bool m(ll a, ll b){
    a = g(a),b = g(b);
    if (a==b) return false;
    if(p[a]>p[b]) swap(a,b);
    p[a] += p[b];
    p[b] = a;
    return true;
  }
};
int min_cardinality(int n) {
  mt19937_64 mt(random_device{}());
  vector<ll> a(n);
  iota(a.begin(),a.end(),0);
  dsu d(n);
  ll run = 1;
  while(run){
    run = 0;
    shuffle(a.begin(),a.end(),mt);
    vector<ll> v;
    for(ll i : a) if(d.p[i]<0) v.push_back(i);
    ll l = 0;
    for(ll i = 0;i<v.size();i++){
      move_inside(v[i]);
      if (i>0&&press_button()>1){
        do{
          move_outside(v[l++]);
        }while(press_button()>1);
        d.m(v[l-1],v[i]);
        run = 1;
      }
    }
    while(l<v.size())move_outside(v[l++]);
  }
  ll ans = -n;
  for(ll i : d.p) if(i<0)ans = max(ans,i);
  return -ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:32:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(ll i = 0;i<v.size();i++){
      |                  ~^~~~~~~~~
insects.cpp:42:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     while(l<v.size())move_outside(v[l++]);
      |           ~^~~~~~~~~

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