Submission #1058167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058167		mychecksedad	Rarest Insects (IOI22_insects)	C++17	0 / 100	76 ms	856 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;
  for(int i = 0; i < n; ++i){
    // if(!used[v[i]]){
      tot++;
      move_inside(v[i]);
      co++;
      int car = press_button();
      if(car > k){
        move_outside(v[i]);
        --co;
      }
    // }
  }
  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 > last_car){
      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 c: a) move_outside(c);
  int l = 1, r = n / a.size(); int ans = r;
  while(l <= r){
    int m = l+r>>1;
    if(is_big(m)){
      ans = m;
      l = m + 1;
    }else{
      r = m - 1;
    }
  }
  return ans;
}

Compilation message (stderr)

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

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