QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#502584#1936. Mobile ComputingRainPPR100 ✓558ms12064kbC++202.3kb2024-08-03 09:53:322024-08-03 09:53:33

Judging History

你现在查看的是最新测评结果

  • [2024-08-03 09:53:33]
  • 评测
  • 测评结果:100
  • 用时:558ms
  • 内存:12064kb
  • [2024-08-03 09:53:32]
  • 提交

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