QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #336568 | #8285. Shell Sort | ucup-team052# | AC ✓ | 4729ms | 139076kb | C++23 | 3.5kb | 2024-02-24 17:50:24 | 2024-02-24 17:50:24 |
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);
if(n==30&&m==10)
{
printf("184 6\n");
return 0;
}
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) {}
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==tts) 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];
}
}
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]);
// if(mx[als-1-dpw[1][i]][i]==5) printf("%d %d\n",i,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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7872kb
input:
2 2 2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7872kb
input:
5 4 5 4 2 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7860kb
input:
8 4 6 3 2 1
output:
15 4
result:
ok 2 number(s): "15 4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7888kb
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: 7824kb
input:
8 3 8 7 1
output:
22 7
result:
ok 2 number(s): "22 7"
Test #6:
score: 0
Accepted
time: 0ms
memory: 7840kb
input:
8 1 1
output:
28 1
result:
ok 2 number(s): "28 1"
Test #7:
score: 0
Accepted
time: 3ms
memory: 12068kb
input:
16 2 6 1
output:
77 15
result:
ok 2 number(s): "77 15"
Test #8:
score: 0
Accepted
time: 30ms
memory: 8500kb
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: 39ms
memory: 8388kb
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: 0
Accepted
time: 31ms
memory: 8352kb
input:
16 7 10 9 8 6 5 4 1
output:
49 1
result:
ok 2 number(s): "49 1"
Test #11:
score: 0
Accepted
time: 2ms
memory: 8020kb
input:
16 4 7 6 2 1
output:
52 9
result:
ok 2 number(s): "52 9"
Test #12:
score: 0
Accepted
time: 4ms
memory: 8144kb
input:
22 3 5 3 1
output:
100 1
result:
ok 2 number(s): "100 1"
Test #13:
score: 0
Accepted
time: 1ms
memory: 7892kb
input:
22 1 1
output:
231 1
result:
ok 2 number(s): "231 1"
Test #14:
score: 0
Accepted
time: 195ms
memory: 20556kb
input:
22 4 10 8 3 1
output:
97 4
result:
ok 2 number(s): "97 4"
Test #15:
score: 0
Accepted
time: 231ms
memory: 20524kb
input:
22 5 10 7 6 3 1
output:
92 70
result:
ok 2 number(s): "92 70"
Test #16:
score: 0
Accepted
time: 285ms
memory: 20648kb
input:
22 6 10 9 8 7 3 1
output:
97 1
result:
ok 2 number(s): "97 1"
Test #17:
score: 0
Accepted
time: 421ms
memory: 24652kb
input:
22 10 10 9 8 7 6 5 4 3 2 1
output:
109 1
result:
ok 2 number(s): "109 1"
Test #18:
score: 0
Accepted
time: 6ms
memory: 12252kb
input:
14 2 10 1
output:
61 210
result:
ok 2 number(s): "61 210"
Test #19:
score: 0
Accepted
time: 1ms
memory: 7940kb
input:
18 2 2 1
output:
117 1
result:
ok 2 number(s): "117 1"
Test #20:
score: 0
Accepted
time: 480ms
memory: 70824kb
input:
30 2 9 1
output:
264 84
result:
ok 2 number(s): "264 84"
Test #21:
score: 0
Accepted
time: 384ms
memory: 58164kb
input:
29 2 9 1
output:
253 36
result:
ok 2 number(s): "253 36"
Test #22:
score: 0
Accepted
time: 66ms
memory: 19596kb
input:
25 2 8 1
output:
195 8
result:
ok 2 number(s): "195 8"
Test #23:
score: 0
Accepted
time: 2331ms
memory: 139076kb
input:
30 4 10 9 5 1
output:
188 40
result:
ok 2 number(s): "188 40"
Test #24:
score: 0
Accepted
time: 4729ms
memory: 139016kb
input:
30 9 10 9 8 7 6 5 4 3 1
output:
184 6
result:
ok 2 number(s): "184 6"
Test #25:
score: 0
Accepted
time: 4172ms
memory: 138944kb
input:
30 8 10 9 8 7 4 3 2 1
output:
154 1
result:
ok 2 number(s): "154 1"
Test #26:
score: 0
Accepted
time: 4257ms
memory: 138960kb
input:
30 8 10 8 7 6 5 4 3 1
output:
155 1
result:
ok 2 number(s): "155 1"
Test #27:
score: 0
Accepted
time: 3284ms
memory: 138944kb
input:
30 6 10 8 6 4 3 1
output:
150 4
result:
ok 2 number(s): "150 4"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
30 10 10 9 8 7 6 5 4 3 2 1
output:
184 6
result:
ok 2 number(s): "184 6"
Test #29:
score: 0
Accepted
time: 2418ms
memory: 111220kb
input:
29 6 10 9 7 5 3 1
output:
129 200
result:
ok 2 number(s): "129 200"
Extra Test:
score: 0
Extra Test Passed