QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#643212 | #6609. Scholomance Academy | ChensenCHX | WA | 2ms | 10032kb | C++23 | 2.7kb | 2024-10-15 19:51:53 | 2024-10-15 19:51:57 |
Judging History
answer
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define Mid (l+r)/2
#define Ls i<<1
#define Rs i<<1|1
#define Lson Ls,l,Mid
#define Rson Rs,Mid+1,r
#define For(i,a,b) for(int i=a;i<=b;i++)
#define FOr(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//tree<ll,null_type,std::less<ll>,splay_tree_tag,tree_order_statistics_node_update>sp;//红黑树是rb_tree_tag
/*
inline int read()
{
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
*/
//parameter begin
#define maxN 1000010
#define M 1000000009
ll n,b[maxN],len,tp,tn,fp,fn,realp,realn,cnt;
long double tpr[maxN],fpr[maxN];
typedef struct
{
ll s;
char c;
}SC;
SC a[maxN];
//parameter end
//function begin
bool cmp(SC& x,SC& y)
{
return x.s<y.s;
}
ll findx(ll x)
{
return lower_bound(b+1,b+len+1,x)-b;
}
//function end
int main ()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//main begin
cin>>n;
fp=tp=fn=tn=0;
cnt=0;
For(i,1,n)
{
cin>>a[i].c>>a[i].s;
b[i]=a[i].s;
if(a[i].c=='+') tp++;
else fp++;
}
if(tp == n || tp == n){
printf("0");
return 0;
}
sort(b+1,b+n+1);
len=unique(b+1,b+n+1)-b-1;
sort(a+1,a+n+1,cmp);
tpr[0]=(long double)tp/((long double)tp+(long double)fn),fpr[0]=(long double)fp/((long double)tn+(long double)fp);
For(i,1,n)
{
if(a[i+1].s==a[i].s) continue;
if(a[i].c=='-')
{
fp--;
tn++;
}
if(a[i-1].c=='+')
{
tp--;
fn++;
}
++cnt;
tpr[cnt]=(long double)tp/((long double)tp+(long double)fn),fpr[cnt]=(long double)fp/((long double)tn+(long double)fp);
}
++cnt;
tpr[cnt]=fpr[cnt]=(long double)1;
fpr[0]=tpr[0]=(long double)1;
long double sum = 0;
for(int i=cnt-1; i>0; i--){
sum = sum + (fpr[i-1]-fpr[i])*tpr[i];
//cout<<fpr[i]<<' '<<tpr[i]<<' '<<sum<<endl;
}
//cout<<fpr[0]<<' '<<tpr[0]<<' '<<sum<<endl;
cout << fixed << setprecision(12) << sum <<"\n";
//main end
return 0;
}
/*
3
+ 2
- 3
- 1
6
+ 7
- 2
- 5
+ 4
- 2
+ 6
8
+ 34
+ 33
+ 26
- 34
- 38
+ 39
- 7
- 27
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10032kb
input:
3 + 2 - 3 - 1
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 10000kb
input:
6 + 7 - 2 - 5 + 4 - 2 + 6
output:
0.555555555556
result:
wrong answer 1st numbers differ - expected: '0.8888889', found: '0.5555556', error = '0.3333333'