QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491471 | #9156. 百万富翁 | georgeyucjr | 15 | 600ms | 85760kb | C++20 | 4.0kb | 2024-07-25 19:45:19 | 2024-07-25 19:45:19 |
Judging History
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