QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #492744 | #9156. 百万富翁 | zfs732 | 100 ✓ | 3963ms | 86468kb | C++23 | 1.4kb | 2024-07-26 15:44:12 | 2024-07-26 15:44:12 |
Judging History
answer
#include "richest.h"
#include <bits/stdc++.h>
int richest(int N, int T, int S) {
std::vector<int> cur;
for (int i = 0; i < N; i++)
cur.emplace_back(i);
std::vector<int> arr{500000, 250000, 125000, 62500, 20833, 3472, 183, 1};
if (T == 1) arr = std::vector<int>{1};
for (auto B: arr) {
int m = (int) cur.size();
std::vector<int> siz;
for (int i = 0; i < B; i++)
siz.emplace_back(m / B);
for (int i = 0; i < m % B; i++)
siz[i]++;
std::vector<int> qA, qB;
for (int i = 0, l = 0; i < B; i++) {
int r = l + siz[i];
for (int j = l; j < r; j++)
for (int k = j + 1; k < r; k++) {
qA.emplace_back(cur[j]);
qB.emplace_back(cur[k]);
}
l = r;
}
auto res = ask(qA, qB);
std::vector<int> tmp;
for (int i = 0, l = 0, tot = 0; i < B; i++) {
int r = l + siz[i];
std::map<int, std::map<int, int>> g;
for (int j = l; j < r; j++)
for (int k = j + 1; k < r; k++) {
int c = res[tot++] == cur[j];
g[j][k] = c, g[k][j] = !c;
}
for (int j = l; j < r; j++) {
int cnt = 0;
for (int k = l; k < r; k++)
cnt += g[j][k];
if (cnt == r - l - 1)
tmp.emplace_back(cur[j]);
}
l = r;
}
cur = tmp;
}
return cur.front();
}
/*
* 1000000 20 2000000 1
*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 3092ms
memory: 67064kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 85
Accepted
time: 3963ms
memory: 86468kb
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: 3052ms
memory: 66672kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 85
Accepted
time: 3829ms
memory: 86368kb
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