QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #493468 | #9156. 百万富翁 | Survivor_winner | 100 ✓ | 1964ms | 86384kb | C++14 | 1.7kb | 2024-07-27 09:33:54 | 2024-07-27 09:33:54 |
Judging History
answer
#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
int p[10] = {0, 1, 183, 3472, 20833, 62500, 125000, 250000, 500000, 1000000};
int richest(int N, int T, int S)
{
if (T == 1)
{
vector<int> v1, v2;
for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) v1.push_back(i), v2.push_back(j);
vector<int> v = ask(v1, v2), cnt(N);
for (auto i : v) cnt[i]++;
for (int i = 1; i <= N; i++) if (cnt[i] == N - 1) return i;
exit(1);
}
vector<int> v;
for (int i = 0; i < 1e6; i++) v.push_back(i);
for (int i = 8; i >= 1; i--)
{
int x = v.size() / p[i], y = v.size() - x * p[i];
vector<int> v1, v2;
int kkk = 0;
for (int j = 1; j <= y; j++)
{
int l = kkk, r = kkk + x;
for (int ii = l; ii <= r; ii++) for (int jj = ii + 1; jj <= r; jj++) v1.push_back(v[ii]), v2.push_back(v[jj]);
kkk += x + 1;
}
for (int j = 1; j <= p[i] - y; j++)
{
int l = kkk, r = kkk + x - 1;
for (int ii = l; ii <= r; ii++) for (int jj = ii + 1; jj <= r; jj++) v1.push_back(v[ii]), v2.push_back(v[jj]);
kkk += x;
}
vector<int> ans = ask(v1, v2);
v.clear();
kkk = 0;
vector<int> cnt(1e6);
for (int j = 1; j <= y; j++)
{
int l = kkk, r = kkk + x * (x + 1) / 2 - 1;
for (int ii = l; ii <= r; ii++)
{
if (++cnt[ans[ii]] == x) v.push_back(ans[ii]);
}
kkk += x * (x + 1) / 2;
}
for (int j = 1; j <= p[i] - y; j++)
{
int l = kkk, r = kkk + x * (x - 1) / 2 - 1;
for (int ii = l; ii <= r; ii++)
{
if (++cnt[ans[ii]] == x - 1) v.push_back(ans[ii]);
}
kkk += x * (x - 1) / 2;
}
}
return v[0];
}
// 183 3472 20833 62500 125000 250000 500000 1000000
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 631ms
memory: 25260kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 85
Accepted
time: 1963ms
memory: 86320kb
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: 611ms
memory: 25220kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 85
Accepted
time: 1964ms
memory: 86384kb
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