oj.uz

답안 #1058355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1058355 2024-08-14T09:32:47 Z aykhn 드문 곤충 (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;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 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 -