QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491471#9156. 百万富翁georgeyucjr15 600ms85760kbC++204.0kb2024-07-25 19:45:192024-07-25 19:45:19

Judging History

你现在查看的是最新测评结果

  • [2024-07-25 19:45:19]
  • 评测
  • 测评结果:15
  • 用时:600ms
  • 内存:85760kb
  • [2024-07-25 19:45:19]
  • 提交

answer

// author: georgeyucjr
#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
#define LOCAL
#endif

#if __cplusplus >= 201100LL
#else
#error Please use C++11 Or Higher CPP version
#endif

using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using arr3 = std ::array<int, 3>;
using arr4 = std ::array<int, 4>;
using pii = std ::pair<int, int>;

#define rep(i, f, t, ...)                                                     \
  for (std ::decay<decltype(f + t)>::type i = f, _END_##i = t, ##__VA_ARGS__; \
       i <= _END_##i; ++i)
#define per(i, f, t, ...)                                                     \
  for (std ::decay<decltype(f + t)>::type i = f, _END_##i = t, ##__VA_ARGS__; \
       i >= _END_##i; --i)
#define eb emplace_back
#define pb push_back
#define mkp make_pair
#define FILEIO(filename) \
  freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout)
#define INLINE_V inline

template <class T, class U>
inline constexpr auto ceil(T&& x, U&& y) {
  return (x > 0 ? (x + y - 1) / y : x / y);
}

template <class T, class U>
inline constexpr auto floor(T&& x, U&& y) {
  return (x > 0 ? x / y : (x - y + 1) / y);
}

template <class T, class U>
inline constexpr auto divmod(T&& x, U&& y) {
  auto&& q = floor(x, y);
  return std ::pair{q, x - q * y};
}

#define ALL(vc) std ::begin(vc), std ::end(vc)

template <class T>
  requires(std ::is_signed_v<T> || std ::is_unsigned_v<T>)
INLINE_V constexpr static T inf = std ::numeric_limits<T>::max() >> 1;

template <std ::ranges ::forward_range R>
inline constexpr auto Sum(R&& r) {
  return std ::accumulate(std ::ranges ::begin(r), std ::ranges ::end(r), 0);
}

template <std ::ranges ::forward_range R, typename T>
inline constexpr auto Sum(R&& r, T init) {
  return std ::accumulate(std ::ranges ::begin(r), std ::ranges ::end(r), init);
}

template <std ::ranges ::forward_range R>
inline constexpr int SZ(R&& x) {
  return std ::size(x);
}

template <class Os, class T>
inline Os& operator<<(Os& os, T& t) {
  for (auto ele : t) os << ele << " ";
  os << "\n";
  return os;
}

template <class T>
inline constexpr void clr_cont(T& cont) {
  T nw;
  cont.swap(nw);
}

inline constexpr auto Abs(const auto& x) { return x < 0 ? -x : x; }
inline constexpr auto sqr(const auto& x) { return x * x; }
inline constexpr auto Max(const auto& x) { return x; }
inline constexpr auto Min(const auto& x) { return x; }
inline constexpr auto Max(const auto& x, const auto& y, const auto&... args) {
  return x < y ? Max(y, args...) : Max(x, args...);
}
inline constexpr auto Min(const auto& x, const auto& y, const auto&... args) {
  return x < y ? Min(x, args...) : Min(y, args...);
}
inline constexpr void chkmax(auto& d, const auto&... x) { d = Max(d, x...); }
inline constexpr void chkmin(auto& d, const auto&... x) { d = Min(d, x...); }

using namespace std;

constexpr int N = 1e6 + 5;

#include "richest.h"

constexpr array<int, 8> Ls = {500000, 250000, 125000, 62500, 20832, 3472, 183, 1};

int richest(int n, int T, int S) {
  if (T == 1) {
    vector<int> v1, v2;
    rep(i, 1, n) rep(j, i + 1, n) v1.eb(i - 1), v2.eb(j - 1);
    auto ans = ask(v1, v2);
    vector<int> cnt(n);
    for (auto i : ans) ++cnt[i];
    rep(i, 0, n - 1) if (cnt[i] == n - 1) return i;
    return 114514;
  } else {
    vector<int> id(n);
    iota(ALL(id), 0);
    rep(_, 0, 7) {
      auto k = Ls[_];
      vector<vector<int>> rec(k);
      rep(i, 0, SZ(id) - 1) rec[i % k].eb(id[i]);
      vector<int> v1, v2;
      rep(t, 0, k - 1) {
        auto tv = rec[t];
        rep(x, 0, SZ(tv) - 1) rep(y, x + 1, SZ(tv) - 1) v1.eb(id[x]),
            v2.eb(id[y]);
      }
      auto ans = ask(v1, v2);
      vector<int> cnt(n, 0);
      for (auto i : ans) ++cnt[i];
      id.resize(k);
      rep(i, 0, k - 1) {
        auto tv = rec[i];
        id[i] = -1;
        for (auto j : tv)
          if (cnt[j] == SZ(tv) - 1) id[i] = j;
      }
    }
    return id[0];
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 15
Accepted
time: 600ms
memory: 25296kb

input:

1000 1 499500 957319859

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Pretest #2:

score: 0
Wrong Answer
time: 76ms
memory: 85760kb

input:

1000000 20 2000000 29091473

output:

Index out of bounds
9775460264716263939
0.000000
6906350380861515327

result:

points 0.0 Index out of bounds


Final Tests

Test #1:

score: 15
Accepted
time: 599ms
memory: 25316kb

input:

1000 1 499500 957319857

output:

Correct
7127326332295218295
1.000000
1331569654267968081

result:

points 1.0 Correct

Test #2:

score: 0
Wrong Answer
time: 79ms
memory: 85552kb

input:

1000000 20 2000000 29091471

output:

Index out of bounds
9775460264716263939
0.000000
6906350380861515327

result:

points 0.0 Index out of bounds