QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#502584 | #1936. Mobile Computing | RainPPR | 100 ✓ | 558ms | 12064kb | C++20 | 2.3kb | 2024-08-03 09:53:32 | 2024-08-03 09:53:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 21;
const int M = 1 << N;
int g[M];
ld wide;
int n, w[N];
namespace s1
{
ld ans;
int root, son[N][2];
int node[N];
void print(int k)
{
if (k == -1)
return;
if (son[k][0] != 0)
cerr << k << " -> " << son[k][0] << endl, print(son[k][0]);
if (son[k][1] != 0)
cerr << k << " -> " << son[k][1] << endl, print(son[k][1]);
}
namespace check
{
ld lest, rest;
void eval(int root, ld pos)
{
lest = min(lest, pos);
rest = max(rest, pos);
int l = son[root][0], r = son[root][1];
if (!l && !r)
return;
ld ldis = node[r] / ld(node[l] + node[r]);
eval(l, pos - ldis);
eval(r, pos - ldis + 1);
}
ld calc()
{
lest = 2e9, rest = -2e9;
eval(2 * n - 1, 0);
return rest - lest;
}
}
void dfs(int now, int cnt)
{
if (cnt == 2 * n - 1)
{
ld res = check::calc();
if (res <= wide && res > ans)
ans = res;
return;
}
for (int l = 1; l <= cnt; ++l)
{
if (now & (1 << (l - 1)))
continue;
for (int r = 1; r <= cnt; ++r)
{
if ((l == r) || (now & (1 << (r - 1))))
continue;
int root = cnt + 1;
node[root] = node[l] + node[r];
son[root][0] = l, son[root][1] = r;
dfs(now | (1 << (l - 1)) | (1 << (r - 1)), root);
}
}
}
ld solve()
{
memset(son, 0, sizeof son);
ans = -1;
for (int i = 1; i <= n; ++i)
node[i] = w[i];
dfs(0, n);
return ans;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 1; i < M; ++i)
g[i] = g[i & (i - 1)] + 1;
int T;
cin >> T;
while (T--)
{
cin >> wide >> n;
for (int i = 1; i <= n; ++i)
cin >> w[i];
ld ans = s1::solve();
if (ans == -1)
printf("-1\n");
else
printf("%.16LF\n", s1::solve());
}
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 100
Accepted
time: 558ms
memory: 12064kb
input:
36 9.0 1 5 1.61 6 1 2 3 4 5 6 1.7807 6 1 2 3 4 5 6 1.7621 6 1 2 3 4 5 6 1.54545 4 1 10 100 1000 1.99955 4 1 10 100 1000 1.14090 4 1 10 100 1000 1.95873 5 1 2 10 100 1000 2.48135 5 1 2 10 100 1000 1.87762 5 1 2 10 100 1000 1.55000 5 1 2 10 100 1000 1.37041 5 1 2 10 100 1000 2.12214 5 1 2 10 100 1000 ...
output:
0.0000000000000000 -1 1.7805364570070452 1.7619047619047619 1.1818181818181818 1.9990917347865577 1.0999910801891000 1.9370629370629371 2.4358974358974359 1.8461538461538462 1.4333244135224333 1.3432343234323432 2.1157249829816201 3.4230642670919078 1.6324097267717446 1.4348607367475292 2.2083333333...
result:
ok 36 numbers