Submission #800567

#	Time	Username	Problem	Language	Result	Execution time	Memory
800567		d4xn	Rarest Insects (IOI22_insects)	C++17	0 / 100	331 ms	296 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(), x.end()
 
const int N = 2e3+3, inf = INT_MAX;
 
mt19937 rng((chrono::steady_clock::now().time_since_epoch().count()) + ((uint64_t) new char));
 
int n, mx, taken, ans;
vector<int> v;
bitset<N> vis;
 
int min_cardinality(int N) {
  // move_inside(i);
  // move_outside(i);
  // press_button(i);
 
  ans = inf;
  n = N;
  v.resize(n);
  for (int i = 0; i < n; i++) v[i] = i;

  // Busco los primeros
  for (int i = 0; i < n; i++) {
    move_inside(i);
    vis[i] = 1;
    if (press_button() > 1) {
      move_outside(i);
      vis[i] = 0;
    }
  }

  // Hago el greedy
  int sz = vis.count();
  taken = sz;
  mx = n-taken+1;
  for (int i = 0; i < sz; i++) {
    shuffle(all(v), rng);
 
    mx = min(mx, n-taken+1);

    int curr = 1;
    vector<int> added;
    for (int j = 0; j < n && curr < mx && curr < ans; j++) {
      int x = v[j];
      if (vis[x]) continue;
 
      move_inside(x);
      if (press_button() == curr+1) {
        vis[x] = 1;
        curr++;
        added.push_back(x);
      }
      else {
        move_outside(x);
      }
    }
 
    for (int& x : added) {
      move_outside(x);
    }
    ans = min(ans, curr);
    taken += curr-1;
  }
  return ans;
}

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

using namespace std;

#define all(x) x.begin(), x.end()

const int N = 2e3+3, inf = INT_MAX;

mt19937 rng((chrono::steady_clock::now().time_since_epoch().count()) + ((uint64_t) new char));

int n, mx, taken, ans, tp[N];
vector<int> v, f;

int min_cardinality(int N) {
  // move_inside(i);
  // move_outside(i);
  // press_button(i);

  memset(tp, -1, sizeof(tp));
  ans = inf;
  n = N;
  v.resize(n);
  for (int i = 0; i < n; i++) v[i] = i;

  // en el primer for los meto todos y intento identificar los que son iguales al primero
  // y los primeros (si el max es 1 y despues de añadir sigue siendo 1, es un primero)
  // quiero saber cuanto vale max
  shuffle(all(v), rng);

  mx = 1;
  int extra = 0;
  bool ok = 1;

  move_inside(v[0]);
  f.push_back(v[0]);
  tp[v[0]] = 0;

  for (int i = 1; i < n; i++) {
    int x = v[i];
    move_inside(x);
    mx = press_button();

    if (ok && mx == i+1) {
      tp[x] = 0;
      extra++;
    }
    else {
      ok = 0;
      if (mx == 1) {
        tp[x] = tp[f.back()]+1;
        f.push_back(x);
      }
    }
  }

  // quito los no primeros
  int curr = 0;
  for (int i = 0; i < n; i++) {
    int x = v[i];
    if (curr < (int)f.size() && f[curr] == x) {
      curr++;
      continue;
    }
    move_outside(x);
  }

  // primer for y ver cuantos son iguales al primero
  shuffle(all(v), rng);
  for (int i = 0; i < n; i++) {
    int x = v[i];
    if (tp[x] != -1) continue;

    move_inside(x);
    if (press_button() > 1) {
      move_outside(x);
    }
    else {
      tp[x] = tp[f.back()]+1;
      f.push_back(x);
    }
  }
  taken = f.size();

  // miro cada grupo
  for (int t = 0; t < (int)f.size(); t++) {
    shuffle(all(v), rng);

    mx = min(mx, n-taken+1);
  
    if (t) extra = 0;
    
    curr = 1; // cuantos he metido?
    vector<int> added;
    for (int i = 0; i < n && curr+extra < mx; i++) {
      int x = v[i];
      if (tp[x] != -1) continue;
      
      move_inside(x);
      if (press_button() == curr+1) {
        tp[x] = t;
        added.push_back(x);
        curr++;
      }
      else {
        move_outside(x);
      }
    }

    for (int& x : added) {
      move_outside(x);
    }

    ans = min(ans, curr+extra);
    taken += curr+extra-1;
  }

  return ans;
  
}
*/

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