比赛 |
noip |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
__卡片游戏 |
最终得分 |
100 |
用户昵称 |
. |
运行时间 |
5.299 s |
代码语言 |
C++ |
内存使用 |
7.55 MiB |
提交时间 |
2016-11-04 21:47:14 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mxn=500010;
int a[mxn],r[mxn],n,s[mxn],t[mxn];
ll sum;
double k;
bool cp(const int x,const int y){
double x1=k*x-s[x],y1=k*y-s[y];
return x1<y1||(x1==y1&&x<y);
}
void ms(int L,int R){
if(L>=R) return;
int mi=(L+R)/2,p,q,i;
ms(L,mi); ms(mi+1,R);
i=L; p=L; q=mi+1;
while(p<=mi||q<=R){
if(q>R||(p<=mi&&r[p]<r[q])){
sum+=R-q+1;
t[i++]=r[p++];
}
else t[i++]=r[q++];
}
for(i=L;i<=R;i++) r[i]=t[i];
}
void sol(){
for(int i=0;i<=n;i++) r[i]=i;
sort(r,r+1+n,cp);
sum=0;
ms(0,n);
}
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
freopen("xgame.in","r",stdin);
freopen("xgame.out","w",stdout);
int i,l,r;
ll c,b,g;
scanf("%d%d%d",&n,&l,&r);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
s[0]=0;
for(i=1;i<=n;i++) s[i]=s[i-1]+a[i];
k=r;
sol(); c=sum;
k=l-0.000001;
sol(); c-=sum;
b=(ll)n*(n+1)/2;
if(c==0){ printf("0\n"); return 0;}
g=gcd(c,b);
c/=g; b/=g;
cout<<c;
if(b>1) cout<<"/"<<b;
cout<<"\n";
return 0;
}