QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698175#5444. Tavern ChessabsabsAC ✓185ms12120kbC++236.2kb2024-11-01 17:58:362024-11-01 17:58:37

Judging History

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

  • [2024-11-01 17:58:37]
  • 评测
  • 测评结果:AC
  • 用时:185ms
  • 内存:12120kb
  • [2024-11-01 17:58:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ull unsigned long long
#define ms(x, y) memset(x, y, sizeof x);
#define debug(x) cout << #x << " = " << x << endl;
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define fre                           \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const double esp = 1e-6;
const ull MOD1 = 1610612741;
const ull MOD2 = 805306457;
const ull BASE1 = 1331;
const ull BASE2 = 131;
#define pre(i, a, b) for (int i = a; i <= b; i++)
#define rep(i, a, b) for (int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()
char *p1, *p2, buf[100000]; // 快读和同步流二者只能选一个
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (ch < 48 || ch > 57)
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (ch >= 48 && ch <= 57)
        x = x * 10 + ch - 48, ch = nc();
    return x * f;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int n, m;
vector<int> g[N];
int a[N], b[N];
int aa[N], bb[N];
double x, y, z;
void dfs(int al, int bo, int who1, int who2, int op,int now)
{
    if (who1 > n)
        who1 -= n;
    if (who2 > m)
        who2 -= m;
    // cout<<al<<" "<<b`o<<" "<<who1<<" "<<who2<<" "<<op<<endl;
    // for(int i=1;i<=n;i++){
    //     cout<<aa[i]<<" ";
    // }
    // cout<<endl;
    // for(int i=1;i<=m;i++)cout<<bb[i]<<" ";
    // cout<<endl<<endl;
    if (al == 0 && bo == 0)
    {
        z+=1.0/now;
        return;
    }
    else if (al == 0)
    {
        y+=1.0/now;
        return;
    }
    else if (bo == 0)
    {
        x+=1.0/now;
        return;
    }
    if (op == 1)
    {
        if (aa[who1] <= 0)
        {
            dfs(al, bo, who1 + 1, who2, op,now);
            return;
        }
        int sum=0;
        for(int i=1;i<=m;i++){
            if(bb[i]>0)sum++;
        }
        for (int i = 1; i <= m; i++)
        {
            if (bb[i] <= 0)
                continue;
            int bl1 = aa[who1], bl2 = bb[i];
            if (bb[i] <= a[who1])
            {
                bb[i] -= a[who1];
                if (aa[who1] <= b[i])
                {
                    aa[who1] -= b[i];
                    dfs(al - 1, bo - 1, who1 + 1, who2, op ^ 1,now*sum);
                    aa[who1] += b[i];
                }
                else
                {
                    aa[who1] -= b[i];
                    dfs(al, bo - 1, who1 + 1, who2, op ^ 1,now*sum);
                    aa[who1] += b[i];
                }
                bb[i] += a[who1];
            }
            else
            {
                bb[i] -= a[who1];
                if (aa[who1] <= b[i])
                {
                    aa[who1] -= b[i];
                    dfs(al - 1, bo, who1 + 1, who2, op ^ 1,now*sum);
                    aa[who1] += b[i];
                }
                else
                {
                    aa[who1] -= b[i];
                    dfs(al, bo, who1 + 1, who2, op ^ 1,now*sum);
                    aa[who1] += b[i];
                }
                bb[i] += a[who1];
            }
        }
    }
    else
    {
        if (bb[who2] <= 0)
        {
            dfs(al, bo, who1, who2 + 1, op,now);
            return;
        }
        int sum=0;
        for(int i=1;i<=n;i++){
            if(aa[i]>0)sum++;
        }
        for (int i = 1; i <= n; i++)
        {
            if (aa[i] <= 0)
                continue;
            int bl1 = aa[i], bl2 = bb[who2];
            if (aa[i] <= b[who2])
            {
                aa[i] -= b[who2];
                if (bb[who2] <= a[i])
                {
                    bb[who2] -= a[i];
                    dfs(al - 1, bo - 1, who1, who2 + 1, op ^ 1,now*sum);
                    bb[who2] += a[i];
                }
                else
                {
                    bb[who2] -= a[i];
                    dfs(al - 1, bo, who1, who2 + 1, op ^ 1,now*sum);
                    bb[who2] += a[i];
                }
                aa[i] += b[who2];
            }
            else
            {
                aa[i] -= b[who2];
                if (bb[who2] <= a[i])
                {
                    bb[who2] = -1;
                    dfs(al, bo - 1, who1, who2 + 1, op ^ 1,now*sum);
                    bb[who2] = bl2;
                }
                else
                {
                    bb[who2] -= a[i];
                    dfs(al, bo, who1, who2 + 1, op ^ 1,now*sum);
                    bb[who2] += a[i];
                }
                aa[i] += b[who2];
            }
        }
    }
    return;
}
void solve()
{
    cin >> n >> m;
    pre(i, 1, n)
    {
        cin >> a[i];
        aa[i] = a[i];
    }
    pre(i, 1, m)
    {
        cin >> b[i];
        bb[i] = b[i];
    }
    if (n > m)//a da b
    {
        dfs(n, m, 1, 1, 1,1);
    }
    else if (n < m)
    {
        dfs(n, m, 1, 1, 0,1);
    }
    else
    {
        dfs(n, m, 1, 1, 1,2);
        dfs(n, m, 1, 1, 0,2);
    }
    // int sum = x + y + z;
    // cout << x << " " << y << " " << z << endl;
    cout << fixed << setprecision(12) << x << " ";
    cout << fixed << setprecision(12) << y << " ";
    cout << fixed << setprecision(12) << z << endl;
}
// #define LOCAL
signed main()
{
    ios
    // fre
#ifdef LOCAL
        freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto start = std::chrono::high_resolution_clock::now();
#endif

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

#ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    cout << "Execution time: "
         << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
         << " ms" << '\n';
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 10128kb

input:

2 3
2 5
3 4 1

output:

0.125000000000 0.750000000000 0.125000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 10060kb

input:

6 6
1 1 4 5 1 4
1 1 4 5 1 4

output:

0.241867283951 0.241867283951 0.516265432099

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 3ms
memory: 12072kb

input:

7 7
1 1 1 1 1 1 1
1 1 1 1 1 1 1

output:

0.000000000000 0.000000000000 1.000000000000

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 10072kb

input:

1 7
7
1 1 1 1 1 1 1

output:

0.000000000000 0.000000000000 1.000000000000

result:

ok 3 numbers

Test #5:

score: 0
Accepted
time: 3ms
memory: 10028kb

input:

2 3
736618938 652769331
328875880 97571721 44608905

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 10000kb

input:

5 4
53585130 731696211 668322278 611205195 158818781
569587984 776042583 745745433 330119007

output:

0.066840277778 0.664351851852 0.268807870370

result:

ok 3 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 10124kb

input:

7 2
578505806 551611151 92903265 403642038 542119417 57334031 307573613
897644535 168524310

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #8:

score: 0
Accepted
time: 3ms
memory: 10068kb

input:

5 6
113196606 64768263 772808463 787707989 500151952
481840741 676847825 4641268 431386165 847736311 169677832

output:

0.136323173868 0.522397183642 0.341279642490

result:

ok 3 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 10024kb

input:

6 6
260666773 527612597 471926610 702232282 559007797 606173983
560573055 928117268 101411867 875949818 907478252 182117037

output:

0.000000000000 0.960819573045 0.039180426955

result:

ok 3 numbers

Test #10:

score: 0
Accepted
time: 3ms
memory: 9884kb

input:

3 3
333377599 3066695 67916629
426841530 865184552 974638244

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 10076kb

input:

1 1
529429019
529428649

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #12:

score: 0
Accepted
time: 0ms
memory: 10080kb

input:

3 3
12886596 817437415 465037461
12886473 817437448 465037967

output:

0.069444444444 0.652777777778 0.277777777778

result:

ok 3 numbers

Test #13:

score: 0
Accepted
time: 9ms
memory: 10076kb

input:

6 6
211213374 319527017 257080158 176742665 53109345 33822515
53109265 319527076 176743175 257080012 211212799 33822353

output:

0.423399959276 0.319386584791 0.257213455933

result:

ok 3 numbers

Test #14:

score: 0
Accepted
time: 0ms
memory: 10024kb

input:

1 2
1
1 1

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #15:

score: 0
Accepted
time: 0ms
memory: 10076kb

input:

1 2
1
1 3

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #16:

score: 0
Accepted
time: 3ms
memory: 10036kb

input:

1 2
2
4 2

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #17:

score: 0
Accepted
time: 2ms
memory: 9940kb

input:

1 2
3
5 5

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 10028kb

input:

1 2
4
1 2

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #19:

score: 0
Accepted
time: 3ms
memory: 9888kb

input:

1 2
5
2 5

output:

0.000000000000 0.000000000000 1.000000000000

result:

ok 3 numbers

Test #20:

score: 0
Accepted
time: 3ms
memory: 12120kb

input:

1 2
5
5 5

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #21:

score: 0
Accepted
time: 0ms
memory: 10072kb

input:

2 2
1 1
1 3

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #22:

score: 0
Accepted
time: 2ms
memory: 10028kb

input:

2 2
1 1
2 3

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #23:

score: 0
Accepted
time: 0ms
memory: 10004kb

input:

2 2
1 4
2 5

output:

0.000000000000 0.500000000000 0.500000000000

result:

ok 3 numbers

Test #24:

score: 0
Accepted
time: 3ms
memory: 10008kb

input:

2 2
2 2
1 4

output:

0.000000000000 0.000000000000 1.000000000000

result:

ok 3 numbers

Test #25:

score: 0
Accepted
time: 2ms
memory: 10028kb

input:

2 2
3 2
4 1

output:

0.000000000000 0.500000000000 0.500000000000

result:

ok 3 numbers

Test #26:

score: 0
Accepted
time: 0ms
memory: 10080kb

input:

2 2
3 3
1 3

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #27:

score: 0
Accepted
time: 0ms
memory: 10084kb

input:

2 2
3 3
2 4

output:

0.000000000000 0.000000000000 1.000000000000

result:

ok 3 numbers

Test #28:

score: 0
Accepted
time: 0ms
memory: 10032kb

input:

2 2
3 3
5 3

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #29:

score: 0
Accepted
time: 2ms
memory: 9884kb

input:

2 2
4 3
2 1

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #30:

score: 0
Accepted
time: 2ms
memory: 10028kb

input:

2 2
4 3
4 4

output:

0.000000000000 1.000000000000 0.000000000000

result:

ok 3 numbers

Test #31:

score: 0
Accepted
time: 2ms
memory: 10132kb

input:

2 2
5 1
5 2

output:

0.125000000000 0.625000000000 0.250000000000

result:

ok 3 numbers

Test #32:

score: 0
Accepted
time: 2ms
memory: 10016kb

input:

2 2
5 1
5 3

output:

0.125000000000 0.625000000000 0.250000000000

result:

ok 3 numbers

Test #33:

score: 0
Accepted
time: 0ms
memory: 10028kb

input:

2 2
5 2
2 3

output:

0.875000000000 0.000000000000 0.125000000000

result:

ok 3 numbers

Test #34:

score: 0
Accepted
time: 2ms
memory: 10080kb

input:

2 2
5 4
1 2

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #35:

score: 0
Accepted
time: 2ms
memory: 10076kb

input:

2 2
5 4
3 5

output:

0.875000000000 0.000000000000 0.125000000000

result:

ok 3 numbers

Test #36:

score: 0
Accepted
time: 2ms
memory: 10004kb

input:

2 2
5 5
1 4

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #37:

score: 0
Accepted
time: 3ms
memory: 9884kb

input:

2 2
5 5
2 2

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #38:

score: 0
Accepted
time: 0ms
memory: 10016kb

input:

1 1
6
6

output:

0.000000000000 0.000000000000 1.000000000000

result:

ok 3 numbers

Test #39:

score: 0
Accepted
time: 3ms
memory: 10036kb

input:

5 5
6 5 9 9 3
3 5 9 9 6

output:

0.297870370370 0.278773148148 0.423356481481

result:

ok 3 numbers

Test #40:

score: 0
Accepted
time: 2ms
memory: 10028kb

input:

6 6
10 2 3 4 5 7
5 2 4 3 10 7

output:

0.254010456854 0.192773705418 0.553215837727

result:

ok 3 numbers

Test #41:

score: 0
Accepted
time: 29ms
memory: 10088kb

input:

7 7
7 6 8 6 7 3 9
7 6 9 8 7 3 6

output:

0.310913751426 0.365768367914 0.323317880660

result:

ok 3 numbers

Test #42:

score: 0
Accepted
time: 4ms
memory: 10068kb

input:

6 6
5 4 7 9 9 10
9 4 9 7 5 10

output:

0.216942435057 0.327856545782 0.455201019162

result:

ok 3 numbers

Test #43:

score: 0
Accepted
time: 2ms
memory: 10084kb

input:

4 4
9 7 10 6
9 7 6 10

output:

0.330873842593 0.262297453704 0.406828703704

result:

ok 3 numbers

Test #44:

score: 0
Accepted
time: 0ms
memory: 10016kb

input:

3 3
3 10 3
3 10 3

output:

0.187500000000 0.187500000000 0.625000000000

result:

ok 3 numbers

Test #45:

score: 0
Accepted
time: 2ms
memory: 10128kb

input:

2 2
3 4
3 4

output:

0.000000000000 0.000000000000 1.000000000000

result:

ok 3 numbers

Test #46:

score: 0
Accepted
time: 47ms
memory: 10132kb

input:

7 7
922750124 99645786 685060385 948410807 266950246 996521461 883971852
266950246 99645786 883971852 685060385 922750124 996521461 948410807

output:

0.363356371416 0.279566405511 0.357077223072

result:

ok 3 numbers

Test #47:

score: 0
Accepted
time: 79ms
memory: 11988kb

input:

7 7
241155912 361580213 393947982 781406405 485516551 277202028 115028196
485516551 361580213 115028196 393947982 241155912 277202028 781406405

output:

0.370176093599 0.278789945303 0.351033961096

result:

ok 3 numbers

Test #48:

score: 0
Accepted
time: 47ms
memory: 12116kb

input:

7 7
565748008 734938287 873800405 879803305 473331973 893190834 623040014
473331973 734938287 623040014 873800405 565748008 893190834 879803305

output:

0.364305908016 0.315603554227 0.320090537756

result:

ok 3 numbers

Test #49:

score: 0
Accepted
time: 98ms
memory: 9944kb

input:

7 7
14 4 6 5 201506030 15 15
4 14 201506030 15 15 6 5

output:

0.178183791652 0.337081509870 0.484734698474

result:

ok 3 numbers

Test #50:

score: 0
Accepted
time: 71ms
memory: 10028kb

input:

7 7
3 2 3 5 784861968 2 1
2 3 784861968 1 2 3 5

output:

0.223075021873 0.316151580233 0.460773397893

result:

ok 3 numbers

Test #51:

score: 0
Accepted
time: 174ms
memory: 10084kb

input:

7 7
8 15 3 9 168061718 2 5
15 8 168061718 5 2 3 9

output:

0.212969595988 0.319962995067 0.467067408942

result:

ok 3 numbers

Test #52:

score: 0
Accepted
time: 64ms
memory: 9888kb

input:

7 7
859736717 19 19 18 13 10 7
7 10 13 18 19 19 859736717

output:

0.393620652595 0.147967266252 0.458412081153

result:

ok 3 numbers

Test #53:

score: 0
Accepted
time: 85ms
memory: 10020kb

input:

7 7
761045932 18 13 11 9 7 6
6 7 9 11 13 18 761045932

output:

0.382467689555 0.147493238655 0.470039071790

result:

ok 3 numbers

Test #54:

score: 0
Accepted
time: 93ms
memory: 10084kb

input:

7 7
379524878 17 16 14 10 6 1
1 6 10 14 16 17 379524878

output:

0.379260293300 0.176536722080 0.444202984620

result:

ok 3 numbers

Test #55:

score: 0
Accepted
time: 94ms
memory: 10084kb

input:

7 7
986258805 329018732 16 14 10 10 4
4 10 10 14 16 329018732 986258805

output:

0.335206523508 0.168228186482 0.496565290010

result:

ok 3 numbers

Test #56:

score: 0
Accepted
time: 92ms
memory: 12080kb

input:

7 7
402437510 39859989 20 20 18 17 7
7 17 18 20 20 39859989 402437510

output:

0.328699473643 0.160263058269 0.511037468088

result:

ok 3 numbers

Test #57:

score: 0
Accepted
time: 111ms
memory: 10024kb

input:

7 7
719895666 88341845 15 11 10 6 5
5 6 10 11 15 88341845 719895666

output:

0.341541058763 0.169436596666 0.489022344571

result:

ok 3 numbers

Test #58:

score: 0
Accepted
time: 158ms
memory: 9864kb

input:

7 7
22 657372492 8 20 531193761 10 21
8 22 20 657372492 531193761 21 10

output:

0.283032035859 0.214331641403 0.502636322739

result:

ok 3 numbers

Test #59:

score: 0
Accepted
time: 185ms
memory: 10128kb

input:

7 7
8 559730577 2 23 543514141 3 24
2 8 23 559730577 543514141 24 3

output:

0.283681616584 0.222015713449 0.494302669968

result:

ok 3 numbers

Test #60:

score: 0
Accepted
time: 133ms
memory: 10108kb

input:

7 7
24 416408320 4 25 698151361 24 15
4 24 25 416408320 698151361 15 24

output:

0.297516368443 0.247286586968 0.455197044590

result:

ok 3 numbers