QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490262 | #9156. 百万富翁 | strcmp# | 88.00004 | 2396ms | 92292kb | C++14 | 1.2kb | 2024-07-25 13:48:11 | 2024-07-25 13:48:11 |
Judging History
answer
#include <bits/stdc++.h>
//#include <windows.h>
using namespace std;
#include "richest.h"
#define rep(i, a, b) for(int i = a; i <= b; i++)
using vec = vector<int>;
using ll = long long int;
constexpr int maxn = 2e6 + 10;
#define ps push_back
int p[35] = { 500000, 250000, 125000, 62500, 20834, 3472, 182, 1 }, cnt[maxn];
int richest(int n, int t, int s) {
if (n <= 1000) {
vec x, y, z;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) x.ps(i), y.ps(j);
}
z = ask(x, y); int ans = 0;
for (int i = 0; i < z.size(); i++) {
++cnt[z[i]];
if (cnt[z[i]] == n - 1) ans = z[i];
}
for (int i = 0; i < z.size(); i++) --cnt[z[i]];
return ans;
}
vec a;
for (int i = 0; i < n; i++) a.push_back(i);
for (int i = 0; i < 8; i++) {
vec x, y;
for (int j = 0; j < a.size(); j++) {
for (int k = j % p[i]; k < j; k += p[i]) if (j != k) x.ps(a[j]), y.ps(a[k]);
}
vec z = ask(x, y), na;
for (int j = 0; j < z.size(); j++) z[j] == x[j] ? ++cnt[y[j]] : ++cnt[x[j]];
for (int j = 0; j < a.size(); j++) if (!cnt[a[j]]) na.ps(a[j]);
for (int j = 0; j < z.size(); j++) z[j] == x[j] ? --cnt[y[j]] : --cnt[x[j]];
a = na;
}
return a[0];
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 625ms
memory: 27328kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 73
Acceptable Answer
time: 2396ms
memory: 92292kb
input:
1000000 20 2000000 29091473
output:
Partially correct Case 2, 73 / 85, maxt = 8, maxs = 1099949 17426524471734973367 0.858824 2728835475266523013
result:
points 0.858824 Partially correct Case 2, 73 / 85, maxt = 8, maxs = 1099949
Final Tests
Test #1:
score: 15
Accepted
time: 625ms
memory: 27348kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 73
Acceptable Answer
time: 2343ms
memory: 91176kb
input:
1000000 20 2000000 29091471
output:
Partially correct Case 2, 73 / 85, maxt = 8, maxs = 1099949 17426524471734973367 0.858824 2728835475266523013
result:
points 0.858824 Partially correct Case 2, 73 / 85, maxt = 8, maxs = 1099949