QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276921#7013. Rikka with Antsucup-team1209#AC ✓20ms3920kbC++203.0kb2023-12-06 13:02:002023-12-06 13:02:00

Judging History

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

  • [2023-12-06 13:02:00]
  • 评测
  • 测评结果:AC
  • 用时:20ms
  • 内存:3920kb
  • [2023-12-06 13:02:00]
  • 提交

answer

#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ;

cs int N = 4e5 + 5; 

int T, n, a[N];
int s1, e1, s2, e2;
pi c[2][2];
pi calc(int a, int b, int c, int d) {
    vector <int> e(n + 1);
    for(int i = a; i != b; i = i % n + 1) {
        e[i] ++; 
    }
    for(int i = c; i != d; i = i % n + 1) {
        e[i] ++; 
    }
    int s1 = 0, s2 = 0; 
    for(int i = a; i != b; i = i % n + 1) {
        if(e[i] == 1) s1 += :: a[i];
        if(e[i] == 2) s1 += 3 * :: a[i];
    }
    for(int i = c; i != d; i = i % n + 1) {
        if(e[i] == 1) s2 += :: a[i];
        if(e[i] == 2) s2 += 3 * :: a[i];
    }
    return pi(s1, s2);
}
double calcc(double b00,double b01,double b10,double b11) {
    double k=b00+b11-b01-b10;
    double t=b11-b01;
    if (fabs(k)<1e-10) {
        if (fabs(t)<1e-10) return 0.5;
        return -1;
    }
    return t/k;
}
pair <double, double> NASH(pi c[2][2]) {
    for (int i=0;i<2;i++) for (int j=0;j<2;j++) swap(c[i][j].first,c[i][j].second);
    double x=calcc(c[0][0].second,c[0][1].second,c[1][0].second,c[1][1].second);
    double y=calcc(c[0][0].first,c[1][0].first,c[0][1].first,c[1][1].first);
    if (x<0||x>1||y<0||y>1) {
        if (x<0||x>1) {
            double w0=c[0][0].second, w1=c[1][0].second;
            if (w0<w1) y=0; else y=1;
            double x0=c[(int)y][0].first;
            double x1=c[(int)y][1].first;
            if (x0<x1) x=0; else x=1;
        }
        else {
            double w0=c[0][0].first, w1=c[0][1].first;
            if (w0<w1) x=0; else x=1;
            double y0=c[0][(int)x].second;
            double y1=c[1][(int)x].second;
            if (y0<y1) y=0; else y=1;
        }
        assert(c[(int)y][(int)x].first<=c[(int)y][((int)x)^1].first);
        assert(c[(int)y][(int)x].second<=c[((int)y)^1][((int)x)].second);
        return c[(int)y][(int)x];
    }
    else {
        assert(fabs(c[0][0].first*y+c[1][0].first*(1-y)-(c[0][1].first*y+c[1][1].first*(1-y)))<1e-10);
        assert(fabs(c[0][0].second*x+c[0][1].second*(1-x)-(c[1][0].second*x+c[1][1].second*(1-x)))<1e-10);
        return {c[0][0].first*y+c[1][0].first*(1-y),c[0][0].second*x+c[0][1].second*(1-x)};
    }
    // for(int i = 0; i < 2; i++)
    // for(int j = 0; j < 2; j++)
    // cout << c[i][j].first << ' ' << c[i][j].second << '\n';
    // return pair <double, double> (0, 0);
}
void Main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cin >> s1 >> e1 >> s2 >> e2; 
    c[0][0] = calc(s1, e1, s2, e2);
    c[0][1] = calc(s1, e1, e2, s2);
    c[1][0] = calc(e1, s1, s2, e2); 
    c[1][1] = calc(e1, s1, e2, s2);
    pair <double, double> ans = NASH(c);
    cout<<setprecision(12)<<fixed<<ans.second<<' '<<ans.first<<'\n';
}

int main() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
    ios :: sync_with_stdio(0), cin.tie(0);
    cin >> T; 
    while(T--) {
        Main();
    }
    return 0; 
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3920kb

input:

2
5
1 5 2 4 3
1 2 3 4
5
1 5 2 4 3
1 3 2 4

output:

1.000000000000 2.000000000000
14.666666666667 14.666666666667

result:

ok 2 cases

Test #2:

score: 0
Accepted
time: 20ms
memory: 3876kb

input:

5000
5
8 22 47 25 13
3 5 3 1
20
9 24 41 8 23 31 48 15 46 5 17 36 29 40 36 43 34 33 29 26
16 4 15 5
3
8 22 33
1 2 2 3
26
18 44 37 21 44 44 5 15 43 44 44 37 19 10 22 14 41 37 42 18 14 34 3 17 30 42
13 2 13 15
26
31 31 41 11 35 49 13 29 33 11 27 6 16 25 47 40 2 33 27 35 35 29 48 35 5 7
17 3 13 3
26
30 ...

output:

72.000000000000 30.000000000000
571.628865979381 571.628865979381
8.000000000000 22.000000000000
378.000000000000 29.000000000000
728.898876404494 728.898876404494
356.000000000000 103.000000000000
509.916981132076 509.916981132075
87.000000000000 63.000000000000
80.000000000000 36.000000000000
157....

result:

ok 5000 cases