QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #336517 | #8285. Shell Sort | ucup-team052# | WA | 36ms | 8396kb | C++23 | 3.9kb | 2024-02-24 17:22:14 | 2024-02-24 17:22:14 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, b, a) for (int i = b; i >= a; i--)
using namespace std;
#define mod 1000000007
int add(int x,int y){return x+y<mod?x+y:x+y-mod;}
int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
int mul(int x,int y){return 1ULL*x*y%mod;}
#define N 35
int n,m,d[N],dsiz[N][N],dpw[N][N];
int inv[1048576][11];
int a[N],tmp[N];
int simulate()
{
int ans=0;
for(int i=2;i<=m;i++)
{
int t=d[i];
for(int j=0;j<t;j++)
{
int cnt1=0,cnt0=0,cntn=0;
for(int k=0;k<dsiz[i][j];k++)
{
if(a[k*t+j]==-1) cntn++;
else if(a[k*t+j]==0) ans+=cnt1,cnt0++;
else cnt1++;
}
for(int k=0;k<dsiz[i][j];k++)
{
if(cntn) cntn--,a[k*t+j]=-1;
else if(cnt0) cnt0--,a[k*t+j]=0;
else cnt1--,a[k*t+j]=1;
}
}
}
return ans;
}
void getinv()
{
const int als=dpw[1][d[1]];
for(int i=0;i<als;i++)
{
for(int j=0;j<d[1];j++)
{
int ts=dsiz[1][j],rem=i/dpw[1][j]%(ts+1);
// printf("%d %d : %d %d\n",i,j,ts,rem);
for(int k=0;k<rem;k++) a[k*d[1]+j]=-1;
for(int k=rem;k<ts;k++) a[k*d[1]+j]=1;
}
for(int j=0;j<n;j++) tmp[j]=a[j];
// for(int j=0;j<n;j++) printf("%d%c",a[j]," \n"[j==n-1]);
for(int j=0;j<d[1];j++)
{
for(int k=0;k<n;k++) a[k]=tmp[k];
int ts=dsiz[1][j],rem=i/dpw[1][j]%(ts+1);
// printf("* %d %d : %d %d\n",i,j,ts,rem*d[1]+j);
if(rem!=ts) a[rem*d[1]+j]=0;
else continue;
// for(int j=0;j<n;j++) printf("%d%c",a[j]," \n"[j==n-1]);
inv[i][j]=simulate();
// printf("%d %d : %d\n",i,j,inv[i][j]);
a[rem*d[1]+j]=1;
}
}
}
int mx[1048576][11],cnt[1048576][11];
signed main()
{
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
// cerr<<sizeof(inv)/1024.0/1024<<endl;
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>d[i],d[i]=min(d[i],n);
for(int i=1;i<=m;i++)
{
for(int j=0;j<d[i];j++) dsiz[i][j]=(n+d[i]-1-j)/d[i];
dpw[i][0]=1; for(int j=1;j<=d[i];j++) dpw[i][j]=dpw[i][j-1]*(dsiz[i][j-1]+1);
}
/*
for(int i=1;i<=m;i++)
{
printf("%d :\n",i);
for(int j=0;j<d[i];j++) printf("%d %d\n",dsiz[i][j],dpw[i][j]);
}
*/
getinv();
const int als=dpw[1][d[1]];
for(int i=0;i<als;i++)
{
if(i==0)
{
for(int j=0;j<d[1];j++) cnt[i][j]=1;
}
int cur=i;
for(int j=0;j<d[1];j++)
{
int ts=dsiz[1][j],rem=cur/dpw[1][j]%(ts+1);
for(int k=0;k<rem;k++) a[k*d[1]+j]=-1;
for(int k=rem;k<ts;k++) a[k*d[1]+j]=1;
}
for(int j=0;j<d[1];j++)
{
int ts=dsiz[1][j],rem=cur/dpw[1][j]%(ts+1);
if(rem!=ts) a[rem*d[1]+j]=0;
else continue;
mx[i][j]+=inv[i][j];
// i j
// printf("%d %d : %d %d\n",i,j,mx[i][j],cnt[i][j]);
// for(int c=0;c<n;c++) printf("%d%c",a[c]," \n"[c==n-1]);
cur+=dpw[1][j];
for(int k=0;k<d[1];k++)
{
int tts=dsiz[1][k],rrem=cur/dpw[1][k]%(tts+1);
if(rrem==ts) continue;
// cur k ! mx[i][j]+inv[cur][k]
if(mx[i][j]>mx[cur][k]) mx[cur][k]=mx[i][j],cnt[cur][k]=0;
if(mx[i][j]==mx[cur][k]) cnt[cur][k]=add(cnt[cur][k],cnt[i][j]);
}
cur-=dpw[1][j];
a[rem*d[1]+j]=1;
}
}
int ans=0,acnt=0;
for(int i=0;i<d[1];i++)
{
if(mx[als-1-dpw[1][i]][i]>ans) ans=mx[als-1-dpw[1][i]][i],acnt=0;
if(mx[als-1-dpw[1][i]][i]==ans) acnt=add(acnt,cnt[als-1-dpw[1][i]][i]);
}
for(int i=0;i<d[1];i++)
{
int r=dsiz[1][i];
ans+=r*(r-1)/2;
}
printf("%d %d\n",ans,acnt);
return 0;
}
/*
1 :
3 1
2 4
2 :
5 1
0 0 : 0
0 1 : 1
1 0 : 1
1 1 : 0
2 0 : 2
2 1 : 0
3 0 : 0
3 1 : 1
4 0 : 0
4 1 : 1
5 0 : 1
5 1 : 0
6 0 : 0
6 1 : 2
7 0 : 0
7 1 : 1
8 0 : 2
8 1 : 0
9 0 : 0
9 1 : 1
10 0 : 1
10 1 : 0
11 0 : 2
11 1 : 0
0 0 : 0 1
0 1 : 1 1
1 0 : 1 1
1 1 : 0 1
2 0 : 3 1
2 1 : 1 1
3 0 : 3 1
3 1 : 4 1
4 0 : 3 1
4 1 : 4 1
5 0 : 4 1
5 1 : 3 1
6 0 : 4 1
6 1 : 6 1
7 0 : 4 2
7 1 : 5 2
8 0 : 6 2
8 1 : 4 3
9 0 : 6 2
9 1 : 7 2
10 0 : 7 3
10 1 : 6 3
11 0 : 9 3
11 1 : 7 3
7 3
11 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7916kb
input:
2 2 2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7900kb
input:
5 4 5 4 2 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 7928kb
input:
8 4 6 3 2 1
output:
15 4
result:
ok 2 number(s): "15 4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 8060kb
input:
8 6 8 7 5 4 2 1
output:
14 2
result:
ok 2 number(s): "14 2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7996kb
input:
8 3 8 7 1
output:
22 7
result:
ok 2 number(s): "22 7"
Test #6:
score: 0
Accepted
time: 0ms
memory: 7888kb
input:
8 1 1
output:
28 1
result:
ok 2 number(s): "28 1"
Test #7:
score: 0
Accepted
time: 3ms
memory: 8004kb
input:
16 2 6 1
output:
77 15
result:
ok 2 number(s): "77 15"
Test #8:
score: 0
Accepted
time: 36ms
memory: 8360kb
input:
16 8 10 9 8 7 6 5 4 1
output:
57 5
result:
ok 2 number(s): "57 5"
Test #9:
score: 0
Accepted
time: 36ms
memory: 8344kb
input:
16 10 10 9 8 7 6 5 4 3 2 1
output:
57 3
result:
ok 2 number(s): "57 3"
Test #10:
score: -100
Wrong Answer
time: 33ms
memory: 8396kb
input:
16 7 10 9 8 6 5 4 1
output:
48 1
result:
wrong answer 1st numbers differ - expected: '49', found: '48'