比赛 noip 评测结果 C
题目名称 __卡片游戏 最终得分 0
用户昵称 Okami 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2016-11-04 19:06:44
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const ll maxn =500005;
ll init(){
	ll x = 0;
	char c = getchar();
	while(c<'0'||c>'9')c = getchar();
	while(c>='0'&&c<='9'){
		x = x*10+c-'0';
		c = getchar();
	}
	return x;
}
ll a[maxn],s[maxn],tmp[maxn],ans;
ll cal(int l ,int r,bool flag){
	if(l>=r)return 0;
	int mid = (l+r)>>1;
	ll ret = cal(l,mid,flag)+cal(mid+1,r,flag);
	int i = l,top = l,j = mid+1;
	while(i<=mid&&j<=r){
		if(s[i]+flag<=s[j])tmp[top++] = s[i++];
		else{
			tmp[top++] = s[j++];
			ret+=mid-i+1;
		}
	}
	while(i<=mid)tmp[top++] = s[i++];
	while(j<=r)tmp[top++] = s[j++];
	for(i = l;i<=r;++i)s[i] = tmp[i];
	return ret;
}
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
int main(){
	freopen("xgame.in","r",stdin);
	freopen("xgame.out","w",stdout);
	ll n,l,r;
	cin>>n>>l>>r;
	s[0] = 0;
	for(int i = 1;i<=n;++i){
		a[i] = init();
		s[i] = s[i-1]+a[i]-r;
	}
	ans = cal(0,n,1);
	s[0] = 0;
	for(int i = 1;i<=n;++i){
		s[i] = s[i-1]+a[i]-l;
	}
	ans -= cal(0,n,0);
	if(ans==0)cout<<"0\n";
	else{
		ll limit = n*(n+1)/2;
		if(ans==limit)cout<<"1\n";
		else{
			ll d = gcd(limit,ans);
			cout<<ans/d<<'/'<<limit/d<<endl;
		}
	}
	fclose(stdin);
	fclose(stdout)
	return 0;
}