Submission #1058263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058263		mychecksedad	Rarest Insects (IOI22_insects)	C++17	57.29 / 100	101 ms	1096 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;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int r(int l, int r){
  return uniform_int_distribution<int>(l, r)(rng);
}
vector<bool> used(N);
vector<int> v;
int n;
int test(int x){
  move_inside(x);
  int last_car = 1;
  vector<int> in;
  in.pb(x);
  for(int i =0 ; i < n; ++i){
    if(!used[v[i]]){
      move_inside(v[i]);
      int car = press_button();
      if(car == last_car){
        move_outside(v[i]);
      }else{
        in.pb(v[i]);
        used[v[i]] = 1;
        last_car++;
      }
    }
  }
  for(int x: in) move_outside(x);
    // cout << x << ' ' << last_car << '\n';
  return last_car;
}
int uniq;
bool is_big(int k){
  int co = 0, tot = 0;
  vi in;
  for(int i = 0; i < n; ++i){
    if(!used[v[i]]){
      tot++;
      move_inside(v[i]);
      co++;
      int car = press_button();
      in.pb(v[i]);
      if(car > k){
        move_outside(v[i]);
        in.pop_back();
        --co;
      }
      // cout << car << ' ' << v[i] << ' ' << k << '\n';
    }
  }
  for(int x: in) move_outside(x);
  // cout << co << ' ' << uniq << ' ' << k << '\n';
  if(k * uniq == co){
    return 1;
  }
  return 0;
}
int min_cardinality(int nn) { n=nn;
  
  for(int i = 0; i < n; ++i) v.pb(i);
  for(int i = 1; i < n; ++i) swap(v[i], v[r(0, i)]); 

  int last_car = 1;
  move_inside(v[0]);
  vector<int> a;
  a.pb(v[0]);
  for(int i = 1; i < n; ++i){
    move_inside(v[i]);
    v.pb(v[i]);
    int car = press_button();
    a.pb(v[i]);
    if(car > 1){
      move_outside(v[i]);
      a.pop_back();
    }
    // cout << i << endl;
  }
  uniq = a.size();
  if(a.size() <= 7){
    int ans = n;
    for(int c: a) used[c] = 1;
    for(int c: a) move_outside(c);
    for(int c: a){
      ans = min(ans, test(c));
    }
    return ans;
  }
  if(a.size() > n/2){
    return 1;
  }
  for(int c: a) used[c] = 1;
  // for(int x: a) cout << x << ' ';
  // cout << "wtf";
  for(int c: a) move_outside(c);
  int l = 0, r = (n - int(a.size())) / a.size(); int ans = r;
  while(l <= r){
    int m = l+r>>1;
    if(is_big(m)){
      // cout << m << ' ';
      ans = m;
      l = m + 1;
    }else{
      r = m - 1;
    }
  }
  return ans + 1;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:99:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |   if(a.size() > n/2){
      |      ~~~~~~~~~^~~~~
insects.cpp:108:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |     int m = l+r>>1;
      |             ~^~
insects.cpp:74:7: warning: unused variable 'last_car' [-Wunused-variable]
   74 |   int last_car = 1;
      |       ^~~~~~~~

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