Submission #1058355

# Submission time Handle Problem Language Result Execution time Memory
1058355 2024-08-14T09:32:47 Z aykhn Rarest Insects (IOI22_insects) C++17
0 / 100
24 ms 600 KB
#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int min_cardinality(int N) 
{
  vector<int> ord(N, 0);
  iota(ord.begin(), ord.end(), 0);
  shuffle(ord.begin(), ord.end(), rng);
  int uni = 0;
  vector<int> v;
  for (int &i : ord)
  {
    move_inside(i);
    if (press_button() > 1) move_outside(i);
    else uni++, v.push_back(i);
  }
  if (uni == 1) return N;
  if (uni == N) return 1;
  vector<int> in(N, 0);
  vector<int> alive(N, 1);
  int cur = v.size();
  for (int &i : v) alive[i] = 0;
  int l = 1, r = N / uni;
  while (l < r)
  {
    int mid = (l + r + 1) >> 1;
    for (int &i : ord)
    {
      if (!alive[i]) continue;
      move_inside(i);
      v.push_back(i);
      cur++;
      in[i] = 1;
      if (press_button() > mid) 
      {
        cur--;
        in[i] = 0;
        move_outside(i);
        v.pop_back();
      }
    }
    if (cur != mid * uni)
    {
      for (int i = 0; i < N; i++)
      {
        if (!in[i]) alive[i] = 0;
      }
      for (int &i : v) 
      {
        cur--;
        move_outside(i), in[i] = 0;
      }
      v.clear();
      r = mid - 1;
    }
    else
    {
      for (int &i : v)
      {
        alive[i] = 0;
        in[i] = 0;
      }
      v.clear();
      l = mid;
    }
  }
  return l;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 368 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 368 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct
8 Correct 8 ms 600 KB Output is correct
9 Correct 24 ms 444 KB Output is correct
10 Correct 15 ms 600 KB Output is correct
11 Correct 17 ms 448 KB Output is correct
12 Correct 12 ms 460 KB Output is correct
13 Incorrect 21 ms 344 KB Wrong answer.
14 Halted 0 ms 0 KB -