oj.uz

Submission #1109950

# Submission time Handle Problem Language Result Execution time Memory
1109950 2024-11-08T08:10:53 Z tibinyte Rarest Insects (IOI22_insects) C++17
10 / 100
 769 ms 932 KB 
#include "insects.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

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

int random(int st, int dr)
{
  uniform_int_distribution<int> dist(st, dr);
  return dist(rng);
}

template <typename t>
using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
struct Mint
{
  int val;
  Mint(int x = 0)
  {
    val = x % mod;
  }
  Mint(long long x)
  {
    val = x % mod;
  }
  Mint operator+(Mint oth)
  {
    return val + oth.val;
  }
  Mint operator-(Mint oth)
  {
    return val - oth.val + mod;
  }
  Mint operator*(Mint oth)
  {
    return 1ll * val * oth.val;
  }
  void operator+=(Mint oth)
  {
    val = (*this + oth).val;
  }
  void operator-=(Mint oth)
  {
    val = (*this - oth).val;
  }
  void operator*=(Mint oth)
  {
    val = (*this * oth).val;
  }
};

Mint powmod(int a, int b)
{
  if (b == 0)
  {
    return 1;
  }
  if (b % 2 == 1)
  {
    return powmod(a, b - 1) * a;
  }
  Mint p = powmod(a, b / 2);
  return p * p;
}

/*
                 .___                 __                 __           .__
  ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
_/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
\  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/

int min_cardinality(int N)
{
  int n = N;
  function<int(int)> get = [&](int x)
  {
    int ans = 0;
    vector<bool> out(n, false);
    for (int i = 0; i < n; ++i)
    {
      move_inside(i);
      if (press_button() == x + 1)
      {
        ans++;
        move_outside(i);
        out[i] = true;
      }
    }
    for (int i = 0; i < n; ++i)
    {
      if (!out[i])
      {
        move_outside(i);
      }
    }
    return ans;
  };
  int ans = 1;
  int distincte = n - get(1);
  int sum = n;
  while (true)
  {
    int ans = sum / distincte;
    int val = n - distincte * ans;
    int frog = get(ans);
    if (val == get(ans))
    {
      return ans;
    }
    sum = n - frog;
  }
  return ans;
}

/*
I cannot take this anymore
Saying everything I've said before
All these words, they make no sense
I find bliss in ignorance
Less I hear, the less you say
You'll find that out anyway
Just like before

Everything you say to me
(Takes me one step closer to the edge)
(And I'm about to break)
I need a little room to breathe
(Cause I'm one step closer to the edge)
(I'm about to break)
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 10 ms 336 KB Output is correct
7 Correct 8 ms 336 KB Output is correct
8 Correct 11 ms 336 KB Output is correct
9 Correct 40 ms 336 KB Output is correct
10 Correct 68 ms 336 KB Output is correct
11 Correct 7 ms 336 KB Output is correct
12 Correct 88 ms 336 KB Output is correct
13 Correct 96 ms 336 KB Output is correct
14 Correct 45 ms 336 KB Output is correct
15 Correct 23 ms 336 KB Output is correct
16 Correct 31 ms 336 KB Output is correct
17 Correct 46 ms 336 KB Output is correct
18 Correct 68 ms 336 KB Output is correct
19 Correct 38 ms 336 KB Output is correct
20 Correct 29 ms 336 KB Output is correct
21 Correct 18 ms 336 KB Output is correct
22 Correct 9 ms 336 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 10 ms 336 KB Output is correct
7 Correct 8 ms 336 KB Output is correct
8 Correct 11 ms 336 KB Output is correct
9 Correct 40 ms 336 KB Output is correct
10 Correct 68 ms 336 KB Output is correct
11 Correct 7 ms 336 KB Output is correct
12 Correct 88 ms 336 KB Output is correct
13 Correct 96 ms 336 KB Output is correct
14 Correct 45 ms 336 KB Output is correct
15 Correct 23 ms 336 KB Output is correct
16 Correct 31 ms 336 KB Output is correct
17 Correct 46 ms 336 KB Output is correct
18 Correct 68 ms 336 KB Output is correct
19 Correct 38 ms 336 KB Output is correct
20 Correct 29 ms 336 KB Output is correct
21 Correct 18 ms 336 KB Output is correct
22 Correct 9 ms 336 KB Output is correct
23 Correct 53 ms 336 KB Output is correct
24 Correct 60 ms 336 KB Output is correct
25 Correct 64 ms 336 KB Output is correct
26 Correct 411 ms 924 KB Output is correct
27 Correct 419 ms 336 KB Output is correct
28 Correct 59 ms 336 KB Output is correct
29 Incorrect 769 ms 428 KB Too many queries.
30 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Partially correct 1 ms 336 KB Output is partially correct
6 Partially correct 2 ms 336 KB Output is partially correct
7 Correct 108 ms 428 KB Output is correct
8 Correct 106 ms 436 KB Output is correct
9 Correct 99 ms 672 KB Output is correct
10 Incorrect 754 ms 932 KB Too many queries.
11 Halted 0 ms 0 KB -