比赛 |
防止浮躁的小练习v0.9 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
__卡片游戏 |
最终得分 |
100 |
用户昵称 |
NVIDIA |
运行时间 |
5.724 s |
代码语言 |
C++ |
内存使用 |
7.15 MiB |
提交时间 |
2016-11-07 15:54:55 |
显示代码纯文本
#include<bits/stdc++.h>
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;
inline int read()
{
int x,f=1;char ch;
while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
return x*f;
}
inline 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);
}
inline 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];
}
inline 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;
}