oj.uz

Submission #1058357

# Submission time Handle Problem Language Result Execution time Memory
1058357 2024-08-14T09:33:02 Z aykhn Rarest Insects (IOI22_insects) C++17
0 / 100
 34 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);
  }
  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;
}

Subtask #1
0 / 10.0

# 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 4 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 440 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 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 4 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 2 ms 440 KB Output is correct
9 Incorrect 2 ms 344 KB Wrong answer.
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 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 1 ms 340 KB Output is correct
4 Correct 1 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 34 ms 456 KB Output is correct
8 Correct 6 ms 600 KB Output is correct
9 Correct 32 ms 428 KB Output is correct
10 Correct 27 ms 344 KB Output is correct
11 Correct 18 ms 444 KB Output is correct
12 Correct 19 ms 600 KB Output is correct
13 Incorrect 25 ms 344 KB Wrong answer.
14 Halted 0 ms 0 KB -