QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31987#1180. The HalfwittersWu_RenAC ✓577ms3816kbC++141.4kb2022-05-14 15:55:282022-05-14 15:55:29

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-14 15:55:29]
  • 评测
  • 测评结果:AC
  • 用时:577ms
  • 内存:3816kb
  • [2022-05-14 15:55:28]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,A,B,C;
int tr[20],b[20];
ll f[2][130],p,o,fac[20];
ll P,Q;
struct nd{
	int w;
	ll c;
}a[130];
void add(int x,int c){
	for(int i=x;i<=n;i+=(i&-i)) tr[i]+=c;
}
int qry(int x){
	int res=0;
	for(int i=x;i;i-=(i&-i)) res+=tr[i];
	return res;
}
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
void sol(){
	scanf("%d%d%d%d%d",&n,&A,&B,&C,&m);
	for(int i=0;i<=n*(n-1)/2;i++) f[0][i]=f[1][i]=0;
	f[0][0]=1,p=0,o=1;
	for(int i=1;i<=n;i++,p^=1,o^=1){
		for(int j=1;j<=i*(i-1)/2;j++) f[p][j]+=f[p][j-1];
		for(int j=0;j<=i*(i-1)/2;j++) f[o][j]=f[p][j]-(j>=i?f[p][j-i]:0);
	}
	for(int i=0;i<=n*(n-1)/2;i++) a[i]={min(B+(n*(n-1)/2-i)*A,i*A),f[p][i]};
	sort(a,a+n*(n-1)/2+1,[](nd &a,nd &b){return a.w<b.w;});
	ll pr=P=Q=0,M=fac[n];
	for(int i=1;i<=n*(n-1)/2;i++){
		pr+=a[i-1].w*a[i-1].c,M-=a[i-1].c;
		P=pr+M*C,Q=fac[n]-M;
		if(P/Q+C>=a[i-1].w&&(P+Q-1)/Q+C<=a[i].w) break;
	}
	assert(Q);
	ll g=gcd(P,Q);P/=g,Q/=g;
	while(m--){
		for(int i=1;i<=n;i++) scanf("%d",&b[i]),tr[i]=0;
		int inv=0;
		for(int i=n;i>=1;i--){
			inv+=qry(b[i]);
			add(b[i],1);
		}
		int w=min(B+(n*(n-1)/2-inv)*A,inv*A);
		if(P>(w-C)*Q) printf("%d/1\n",w);
		else printf("%lld/%lld\n",P+C*Q,Q);
	}
}
int main(){
	for(int i=fac[0]=1;i<=16;i++) fac[i]=i*fac[i-1];
	int T;
	scanf("%d",&T);
	while(T--) sol();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3720kb

input:

1
6 1 1 1 3
1 2 3 4 5 6
5 4 3 2 1 6
6 4 2 1 3 5

output:

0/1
6/1
2771/428

result:

ok 3 tokens

Test #2:

score: 0
Accepted
time: 25ms
memory: 3816kb

input:

10
3 3 2 1 6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
4 7 4 5 24
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
7 1 1 1 5040
1 2 3 4 5 6 7
1 2 3 4 5 7 6
1 2 3 4...

output:

0/1
3/1
3/1
7/2
7/2
2/1
0/1
7/1
7/1
14/1
14/1
169/9
7/1
14/1
14/1
169/9
169/9
18/1
14/1
169/9
169/9
18/1
18/1
11/1
169/9
18/1
18/1
11/1
11/1
4/1
0/1
1/1
1/1
2/1
2/1
3/1
1/1
2/1
2/1
3/1
3/1
4/1
2/1
3/1
3/1
4/1
4/1
5/1
3/1
4/1
4/1
5/1
5/1
6/1
1/1
2/1
2/1
3/1
3/1
4/1
2/1
3/1
3/1
4/1
4/1
5/1
3/1
4/1
4/1...

result:

ok 40350 tokens

Test #3:

score: 0
Accepted
time: 142ms
memory: 3696kb

input:

20
10 426 575 522 5000
1 2 3 4 5 6 7 8 9 10
1 2 3 5 4 6 7 8 9 10
1 2 3 5 4 6 8 7 9 10
10 9 8 7 6 4 5 3 2 1
10 9 8 7 6 4 3 5 2 1
1 2 5 3 4 7 6 8 9 10
10 9 8 7 6 4 3 5 2 1
1 2 5 3 4 6 8 7 9 10
1 2 5 4 3 6 8 7 9 10
1 2 5 4 3 6 8 7 10 9
1 2 5 4 3 6 8 10 7 9
9 10 7 8 6 3 4 5 2 1
1 5 2 4 3 6 8 7 10 9
9 10...

output:

0/1
426/1
852/1
1001/1
1427/1
1278/1
1427/1
1278/1
1704/1
2130/1
2556/1
2705/1
2556/1
3557/1
3983/1
3557/1
3408/1
3557/1
2556/1
3557/1
3408/1
2982/1
3983/1
4409/1
3983/1
3834/1
4835/1
3834/1
4835/1
4409/1
4260/1
4686/1
5112/1
5261/1
5687/1
5538/1
6539/1
6965/1
6816/1
6965/1
5964/1
6113/1
5112/1
4686...

result:

ok 100000 tokens

Test #4:

score: 0
Accepted
time: 577ms
memory: 3772kb

input:

100000
10 426 575 522 1
1 7 6 10 5 9 8 3 4 2
11 218 389 645 1
7 2 3 1 5 11 10 6 9 8 4
12 711 600 618 1
10 12 8 4 6 2 11 9 3 1 5 7
13 340 506 679 1
10 12 8 5 13 2 4 11 9 7 6 1 3
14 310 991 449 1
4 11 1 6 9 5 7 13 14 3 2 10 8 12
15 754 994 657 1
13 5 4 11 8 6 10 12 2 15 9 14 3 1 7
16 138 214 312 1
6 4...

output:

10994755857/1407178
4796/1
16242/1
8326/1
11160/1
1817533830801332/60548706503
27453558003082090/3915750882281
30696603822060551/1081224825026
97162151240085293/4773192608806
21755161877455501/1164585836261
408150504548125/19169510077
27131/1
37671948528423792/1164585836261
37393/1
660/1
77609382402...

result:

ok 100000 tokens