QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#767772#5444. Tavern ChessJasonLee#WA 23ms3996kbC++144.8kb2024-11-20 22:07:382024-11-20 22:07:38

Judging History

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

  • [2024-11-20 22:07:38]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:3996kb
  • [2024-11-20 22:07:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using atk_hp_sum = pair<pair<long long, long long>, long long>;

double awin, bwin, tie1;


void dfs(bool a_st, const vector<atk_hp_sum>& a, const vector<atk_hp_sum>& b, double p)
{
    if (a_st) {
        int b_size = b.size();
        for (int i = 0; i < b.size(); i++) {
            vector<atk_hp_sum> atemp = a, btemp = b;
            int a_id = 0, b_id = i;
            long long aminn = 0;
            for (int j = 0; j < a.size(); j++) {
                aminn = min(a[j].second, aminn);
            }
            for (int j = 0; j < a.size(); j++) {
                if (aminn == a[j].second) {
                    a_id = j;
                    break;
                }
            }
            atemp[a_id].second++;
            atemp[a_id].first.second -= btemp[b_id].first.first;
            btemp[b_id].first.second -= atemp[a_id].first.first;
            vector<atk_hp_sum> outa, outb;
            bool adie = false, bdie = false;
            if (atemp[a_id].first.second <= 0) {
                adie = true;
            }
            if (btemp[b_id].first.second <= 0) {
                bdie = true;
            }
            for (int j = 0; j < atemp.size(); j++) {
                if (!(j == a_id && adie == true)) {
                    outa.push_back(atemp[j]);
                }
            }
            for (int j = 0; j < btemp.size(); j++) {
                if (!(j == b_id && bdie == true)) {
                    outb.push_back(btemp[j]);
                }
            }
            bool endit = false;
            if (outa.size() == 0 && outb.size() == 0) {
                tie1 += p / b_size;
                endit = true;
            }
            else if (outa.size() == 0) {
                bwin += p / b_size;
                endit = true;
            }
            else if (outb.size() == 0) {
                awin += p / b_size;
                endit = true;
            }
            if (!endit)
                dfs(!a_st, outa, outb, 1.0 * p / b_size);
        }
    }
    else {
        int a_size = a.size();
        for (int i = 0; i < a.size(); i++) {
            vector<atk_hp_sum> atemp = a, btemp = b;
            int a_id = i, b_id = 0;
            long long bminn = 0;
            for (int j = 0; j < b.size(); j++) {
                bminn = min(b[j].second, bminn);
            }
            for (int j = 0; j < b.size(); j++) {
                if (bminn == b[j].second) {
                    b_id = j;
                    break;
                }
            }
            btemp[b_id].second++;
            atemp[a_id].first.second -= btemp[b_id].first.first;
            btemp[b_id].first.second -= atemp[a_id].first.first;
            vector<atk_hp_sum> outa, outb;
            bool adie = false, bdie = false;
            if (atemp[a_id].first.second <= 0) {
                adie = true;
            }
            if (btemp[b_id].first.second <= 0) {
                bdie = true;
            }
            for (int j = 0; j < atemp.size(); j++) {
                if (!(j == a_id && adie == true)) {
                    outa.push_back(atemp[j]);
                }
            }
            for (int j = 0; j < btemp.size(); j++) {
                if (!(j == b_id && bdie == true)) {
                    outb.push_back(btemp[j]);
                }
            }
            bool endit = false;
            if (outa.size() == 0 && outb.size() == 0) {
                tie1 += p / a_size;
                endit = true;
            }
            else if (outa.size() == 0) {
                bwin += p / a_size;
                endit = true;
            }
            else if (outb.size() == 0) {
                awin += p / a_size;
                endit = true;
            }
            if (!endit)
                dfs(!a_st, outa, outb, 1.0 * p / a_size);
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<atk_hp_sum> a, b;
    for (int i = 0; i < n; i++) {
        long long temp;
        cin >> temp;
        atk_hp_sum t;
        t.first.first = t.first.second = temp;
        t.second = 0;
        a.push_back(t);
    }
    for (int j = 0; j < m; j++) {
        long long temp;
        cin >> temp;
        atk_hp_sum t;
        t.first.first = t.first.second = temp;
        t.second = 0;
        b.push_back(t);
    }
    if (a.size() > b.size()) {
        awin = 0, bwin = 0, tie1 = 0;
        dfs(true, a, b, 1.0);
    }
    else if (a.size() < b.size()) {
        awin = 0, bwin = 0, tie1 = 0;
        dfs(false, a, b, 1.0);
    }
    else {
        awin = 0, bwin = 0, tie1 = 0;
        dfs(true, a, b, 0.5);
        dfs(false, a, b, 0.5);
    }
    cout << fixed << setprecision(12) << awin << " " << bwin << " " << tie1 << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3768kb

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: 5ms
memory: 3820kb

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: 2ms
memory: 3996kb

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: 0ms
memory: 3980kb

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: 0ms
memory: 3684kb

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: 0ms
memory: 3760kb

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: 0ms
memory: 3760kb

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: 0ms
memory: 3708kb

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: 16ms
memory: 3772kb

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: 0ms
memory: 3980kb

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: 3904kb

input:

1 1
529429019
529428649

output:

1.000000000000 0.000000000000 0.000000000000

result:

ok 3 numbers

Test #12:

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

input:

3 3
12886596 817437415 465037461
12886473 817437448 465037967

output:

0.069444444444 0.652777777778 0.277777777778

result:

ok 3 numbers

Test #13:

score: -100
Wrong Answer
time: 23ms
memory: 3688kb

input:

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

output:

0.423484835820 0.319664362569 0.256850801612

result:

wrong answer 1st numbers differ - expected: '0.4234000', found: '0.4234848', error = '0.0000849'