QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #891823 | #8285. Shell Sort | open your brain (Zhi Zhang, Yanru Guan, Jianfeng Zhu)# | AC ✓ | 795ms | 16184kb | C++14 | 2.1kb | 2025-02-09 18:02:12 | 2025-02-09 18:02:13 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;
const int N=1048576+10;
using namespace std;
int n,m,k,d[20],pr[20],b[20],pos[20],g[20],h[40],nxt[20];
int f[N];
ll y[N];
bool p[40];
void chkmax(int S,int ff,ll yy){
if(f[S]<ff){
f[S]=ff;
y[S]=yy;
}
else if(f[S]==ff) y[S]+=yy;
}
void sol(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d",&d[i]),d[i]=min(d[i],n);
k=d[1];
int res=0;
pr[0]=1;
for(int i=0;i<k;i++){
int sz=(n-i+k-1)/k;
pr[i+1]=pr[i]*(sz+1);
res+=sz*(sz-1)/2;
}
f[0]=0,y[0]=1;
for(int S=1;S<pr[k];S++){
for(int j=0;j<k;j++) b[j]=S%pr[j+1]/pr[j];
for(int i=0;i<n;i++) p[i]=0;
for(int j=0;j<k;j++) if(b[j]>0){
pos[j]=j+(b[j]-1)*k,g[j]=0;
for(int i=j+b[j]*k;i<n;i+=k) p[i]=1;
}
else{
for(int i=j;i<n;i+=k) p[i]=1;
}
for(int l=2;l<=m;l++){
for(int j=0;j<d[l];j++){
int cnt[2]={};
for(int i=j;i<n;i+=d[l]){
h[i]=cnt[1];
cnt[p[i]]++;
}
nxt[j]=j+(cnt[0]-1)*d[l];
for(int i=j;i<n;i+=d[l]){
if((cnt[0]--)>0) p[i]=0;
else p[i]=1;
}
}
for(int j=0;j<k;j++) if(b[j]>0){
g[j]+=h[pos[j]];
pos[j]=nxt[pos[j]%d[l]];
}
// if(S==4){
// for(int j=0;j<k;j++) printf("%d ",b[j]);
// puts("");
// for(int j=0;j<k;j++) printf("%d ",g[j]);
// puts("");
// for(int i=0;i<n;i++) printf("%d ",p[i]);
// puts("");
// }
}
f[S]=-1e9,y[S]=0;
for(int j=0;j<k;j++) if(b[j]>0){
// printf("%d %d\n",S,S-pr[j]);
chkmax(S,f[S-pr[j]]+g[j],y[S-pr[j]]);
}
// printf("%d %d %lld\n",S,f[S],y[S]);
}
printf("%d %lld\n",f[pr[k]-1]+res,y[pr[k]-1]);
}
int main(){
int T=1;
// scanf("%d",&T);
while(T--) sol();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5972kb
input:
2 2 2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5972kb
input:
5 4 5 4 2 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 5968kb
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: 5972kb
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: 0ms
memory: 5804kb
input:
8 3 8 7 1
output:
22 7
result:
ok 2 number(s): "22 7"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
8 1 1
output:
28 1
result:
ok 2 number(s): "28 1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
16 2 6 1
output:
77 15
result:
ok 2 number(s): "77 15"
Test #8:
score: 0
Accepted
time: 6ms
memory: 5876kb
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: 7ms
memory: 5968kb
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: 5ms
memory: 5972kb
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: 1ms
memory: 5964kb
input:
16 4 7 6 2 1
output:
52 9
result:
ok 2 number(s): "52 9"
Test #12:
score: 0
Accepted
time: 1ms
memory: 5968kb
input:
22 3 5 3 1
output:
100 1
result:
ok 2 number(s): "100 1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 5968kb
input:
22 1 1
output:
231 1
result:
ok 2 number(s): "231 1"
Test #14:
score: 0
Accepted
time: 33ms
memory: 6612kb
input:
22 4 10 8 3 1
output:
97 4
result:
ok 2 number(s): "97 4"
Test #15:
score: 0
Accepted
time: 38ms
memory: 6608kb
input:
22 5 10 7 6 3 1
output:
92 70
result:
ok 2 number(s): "92 70"
Test #16:
score: 0
Accepted
time: 46ms
memory: 8836kb
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: 66ms
memory: 8752kb
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: 1ms
memory: 5968kb
input:
14 2 10 1
output:
61 210
result:
ok 2 number(s): "61 210"
Test #19:
score: 0
Accepted
time: 0ms
memory: 5968kb
input:
18 2 2 1
output:
117 1
result:
ok 2 number(s): "117 1"
Test #20:
score: 0
Accepted
time: 74ms
memory: 12844kb
input:
30 2 9 1
output:
264 84
result:
ok 2 number(s): "264 84"
Test #21:
score: 0
Accepted
time: 59ms
memory: 11392kb
input:
29 2 9 1
output:
253 36
result:
ok 2 number(s): "253 36"
Test #22:
score: 0
Accepted
time: 12ms
memory: 6604kb
input:
25 2 8 1
output:
195 8
result:
ok 2 number(s): "195 8"
Test #23:
score: 0
Accepted
time: 375ms
memory: 16128kb
input:
30 4 10 9 5 1
output:
188 40
result:
ok 2 number(s): "188 40"
Test #24:
score: 0
Accepted
time: 748ms
memory: 16100kb
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: 636ms
memory: 16184kb
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: 680ms
memory: 16140kb
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: 526ms
memory: 16176kb
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: 795ms
memory: 16088kb
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: 389ms
memory: 15424kb
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