QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31987 | #1180. The Halfwitters | Wu_Ren | AC ✓ | 577ms | 3816kb | C++14 | 1.4kb | 2022-05-14 15:55:28 | 2022-05-14 15:55:29 |
Judging History
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