QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#638947 | #7013. Rikka with Ants | tarjen | AC ✓ | 23ms | 3888kb | C++20 | 3.0kb | 2024-10-13 17:23:19 | 2024-10-13 17:23:23 |
Judging History
answer
//copied from bai lan ren wo ye bai lan le dui bu qi
#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: 0ms
memory: 3884kb
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: 23ms
memory: 3888kb
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