QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#488174 | #9156. 百万富翁 | lfxxx | 100 ✓ | 2358ms | 99584kb | C++14 | 1.6kb | 2024-07-23 17:20:16 | 2024-07-23 17:20:18 |
Judging History
answer
#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
namespace t1 {
int n = 1000, cnt[1005];
int solve()
{
memset(cnt, 0, sizeof cnt);
vector<int>a, b;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
a.emplace_back(i);
b.emplace_back(j);
}
}
vector<int> c = ask(a, b);
for (int x : c) ++cnt[x];
return max_element(cnt + 1, cnt + 1 + n) - cnt;
}
}
vector<int>v, vv, a, b, c;
int t[] = {500000, 250000, 125000, 62500, 20833, 3472, 183, 1}, cnt[1000005], tot = 0;
inline void query(int l, int r)
{
for (int i = l; i <= r; ++i) {
for (int j = l; j < i; ++j) {
a.emplace_back(v[i]);
b.emplace_back(v[j]);
}
}
}
inline int query2(int l, int r)
{
for (int i = l; i <= r; ++i) cnt[v[i]] = 0;
for (int i = l; i <= r; ++i) {
for (int j = l; j < i; ++j) {
++cnt[c[tot++]];
}
}
int id = l;
for (int i = l + 1; i <= r; ++i) {
if (cnt[v[i]] > cnt[v[id]]) {
id = i;
}
}
return v[id];
}
int richest(int N, int T, int S) {
if (T == 1) return t1::solve();
v.resize(N);
for (int i = 0; i < N; ++i) v[i] = i;
for (int k = 0; v.size() > 1; ++k) {
// for (int x : v) cerr << x << ' '; cerr << '\n';
tot = 0;
a.clear(), b.clear(), vv.clear();
int cnt = t[k], L = 0;
for (int i = 0; i < cnt; ++i) {
query(L, L + v.size() / cnt + (i < v.size() % cnt) - 1);
L += v.size() / cnt + (i < v.size() % cnt);
}
c = ask(a, b);
L = 0;
for (int i = 0; i < cnt; ++i) {
vv.emplace_back(query2(L, L + v.size() / cnt + (i < v.size() % cnt) - 1));
L += v.size() / cnt + (i < v.size() % cnt);
}
v = vv;
}
return v[0];
}
詳細信息
Pretests
Pretest #1:
score: 15
Accepted
time: 621ms
memory: 23012kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 85
Accepted
time: 2336ms
memory: 99584kb
input:
1000000 20 2000000 29091473
output:
Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944 7610580723948932399 1.000000 1331569654267968081
result:
points 1.0 Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944
Final Tests
Test #1:
score: 15
Accepted
time: 628ms
memory: 22884kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 85
Accepted
time: 2358ms
memory: 96728kb
input:
1000000 20 2000000 29091471
output:
Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944 7610580723948932399 1.000000 1331569654267968081
result:
points 1.0 Correct Case 2, 85 / 85, maxt = 8, maxs = 1099944