QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#808265 | #9156. 百万富翁 | Nelofus | 100 ✓ | 2893ms | 106732kb | C++20 | 1.9kb | 2024-12-10 19:08:25 | 2024-12-10 19:08:25 |
Judging History
answer
// Code by Heratino & Nelofus
#include <bits/stdc++.h>
#include "richest.h"
using i64 = long long;
std::vector<int> ask(std::vector<int> a, std::vector<int> b);
std::vector<int> reduceAtoB(int a, int b, std::vector<int> vec) {
assert(a == vec.size());
std::vector<std::vector<int>> g(b);
std::vector<int> ans(b);
int l = 0;
for (int i = 0; i < b; i++) {
int r;
if (i < a % b)
r = l + a / b + 1;
else
r = l + a / b;
for (int j = l; j < r; j++)
g[i].push_back(vec[j]);
l = r;
}
assert(l == a);
// Part 2
std::vector<int> qa, qb;
std::vector<int> ap, bp;
std::vector<int> gl, gr;
auto SetToOne = [&](std::vector<int> s) {
int n = s.size();
gl.push_back(qa.size());
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
qa.push_back(s[i]), qb.push_back(s[j]), ap.push_back(i), bp.push_back(j);
gr.push_back(qa.size());
};
for (int i = 0; i < b; i++)
SetToOne(g[i]);
std::vector<int> qc = ask(qa, qb);
// Part 3
auto Recover = [&](const int &x) {
int n = g[x].size();
std::vector<int> cnt(n, 0);
for (int i = gl[x]; i < gr[x]; i++) {
if (qc[i] == qa[i])
cnt[ap[i]]++;
if (qc[i] == qb[i])
cnt[bp[i]]++;
}
for (int i = 0; i < n; i++)
if (cnt[i] == n - 1)
return g[x][i];
assert(0);
return -1;
};
for (int i = 0; i < b; i++)
ans[i] = Recover(i);
return ans;
}
int richest(int N, int T, int S) {
std::vector<int> ans(N);
for (int i = 0; i < N; i++) ans[i] = i;
if (N == 1000) {
ans = reduceAtoB(1000, 1, ans);
} else {
// 1000000 500000 250000 125000 62500 20832 3472 183 1
ans = reduceAtoB(1000000, 500000, ans);
ans = reduceAtoB(500000, 250000, ans);
ans = reduceAtoB(250000, 125000, ans);
ans = reduceAtoB(125000, 62500, ans);
ans = reduceAtoB(62500, 20832, ans);
ans = reduceAtoB(20832, 3472, ans);
ans = reduceAtoB(3472, 183, ans);
ans = reduceAtoB(183, 1, ans);
}
return ans[0];
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 612ms
memory: 30320kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 85
Accepted
time: 2885ms
memory: 106732kb
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: 613ms
memory: 28760kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 85
Accepted
time: 2893ms
memory: 105964kb
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