QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #844159 | #8228. 排序 | Hanghang | 100 ✓ | 1884ms | 19328kb | C++23 | 1.4kb | 2025-01-05 16:05:07 | 2025-01-05 16:05:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define popc __builtin_popcount
const int N=33,M=2e6+3,H=1e9+7;
int n,m,bas,a[13],sz[13],pos[N][N],val[N][N],col[N],d[N],f[M],g[M];
int Ha(int *tmp)
{
int s=0;
for(int i=0;i<d[1];i++)s=s*bas+tmp[i];
return s;
}
int Ans(int p)
{
int s=0,S=0;
for(int i=0;i<n;i++)S|=col[i]*(1<<i);
for(int t=2;t<=m;t++)
{
int T=0,v=p%d[t];
s+=popc((S&val[t][v])>>p);p=v+popc(S&val[t][v])*d[t];
for(int i=0;i<d[t];i++)T|=val[t][i]&((1<<min(30,d[t]*popc(S&val[t][i])))-1);
S=T;
}
return s;
}
void Solve(int S)
{
for(int i=d[1]-1,v=S;i>=0;i--)a[i]=v%bas,v/=bas;
for(int i=0;i<d[1];i++)if(a[i]>sz[i])return;
for(int i=0;i<n;i++)col[i]=1;
for(int i=0;i<d[1];i++)for(int t=sz[i]-a[i]+1;t<=sz[i];t++)col[pos[i][t]]=0;
for(int i=0;i<d[1];i++)if(a[i]<sz[i])
{
int p=pos[i][sz[i]-a[i]];col[p]=0;a[i]++;
int v=Ans(p),T=Ha(a);a[i]--;col[p]=1;
if(f[S]+v>f[T])f[T]=f[S]+v,g[T]=g[S];
else if(f[S]+v==f[T])g[T]=(g[T]+g[S])%H;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>d[i];
for(int t=1;t<=m;t++)for(int i=0;i<d[t];i++)for(int j=i;j<n;j+=d[t])val[t][i]|=1<<j;
for(int i=0;i<d[1];i++)for(int j=i;j<n;j+=d[1])pos[i][++sz[i]]=j;
bas=*max_element(sz,sz+d[1])+1;int dt=0;
for(int i=0;i<d[1];i++)dt+=sz[i]*(sz[i]-1)/2;
memset(f,0xcf,sizeof(f));f[0]=0;g[0]=1;
for(int S=0;S<M;S++)if(g[S]&&f[S]>=0)Solve(S);
cout<<f[Ha(sz)]+dt<<" "<<g[Ha(sz)];
}
詳細信息
Subtask #1:
score: 18
Accepted
Test #1:
score: 18
Accepted
time: 0ms
memory: 12364kb
input:
2 2 2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 18
Accepted
time: 4ms
memory: 13228kb
input:
5 4 5 4 2 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #3:
score: 18
Accepted
time: 0ms
memory: 13264kb
input:
8 4 6 3 2 1
output:
15 4
result:
ok 2 number(s): "15 4"
Test #4:
score: 18
Accepted
time: 0ms
memory: 11460kb
input:
8 6 8 7 5 4 2 1
output:
14 2
result:
ok 2 number(s): "14 2"
Test #5:
score: 18
Accepted
time: 3ms
memory: 12884kb
input:
8 3 8 7 1
output:
22 7
result:
ok 2 number(s): "22 7"
Test #6:
score: 18
Accepted
time: 3ms
memory: 12748kb
input:
8 1 1
output:
28 1
result:
ok 2 number(s): "28 1"
Subtask #2:
score: 27
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 27
Accepted
time: 2ms
memory: 12456kb
input:
16 2 6 1
output:
77 15
result:
ok 2 number(s): "77 15"
Test #8:
score: 27
Accepted
time: 18ms
memory: 11720kb
input:
16 8 10 9 8 7 6 5 4 1
output:
57 5
result:
ok 2 number(s): "57 5"
Test #9:
score: 27
Accepted
time: 20ms
memory: 12512kb
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: 27
Accepted
time: 16ms
memory: 12740kb
input:
16 7 10 9 8 6 5 4 1
output:
49 1
result:
ok 2 number(s): "49 1"
Test #11:
score: 27
Accepted
time: 2ms
memory: 12656kb
input:
16 4 7 6 2 1
output:
52 9
result:
ok 2 number(s): "52 9"
Subtask #3:
score: 21
Accepted
Dependency #2:
100%
Accepted
Test #12:
score: 21
Accepted
time: 5ms
memory: 13064kb
input:
22 3 5 3 1
output:
100 1
result:
ok 2 number(s): "100 1"
Test #13:
score: 21
Accepted
time: 3ms
memory: 13284kb
input:
22 1 1
output:
231 1
result:
ok 2 number(s): "231 1"
Test #14:
score: 21
Accepted
time: 69ms
memory: 18120kb
input:
22 4 10 8 3 1
output:
97 4
result:
ok 2 number(s): "97 4"
Test #15:
score: 21
Accepted
time: 89ms
memory: 18216kb
input:
22 5 10 7 6 3 1
output:
92 70
result:
ok 2 number(s): "92 70"
Test #16:
score: 21
Accepted
time: 112ms
memory: 16944kb
input:
22 6 10 9 8 7 3 1
output:
97 1
result:
ok 2 number(s): "97 1"
Test #17:
score: 21
Accepted
time: 166ms
memory: 17036kb
input:
22 10 10 9 8 7 6 5 4 3 2 1
output:
109 1
result:
ok 2 number(s): "109 1"
Subtask #4:
score: 10
Accepted
Test #18:
score: 10
Accepted
time: 0ms
memory: 12776kb
input:
14 2 10 1
output:
61 210
result:
ok 2 number(s): "61 210"
Test #19:
score: 10
Accepted
time: 0ms
memory: 11624kb
input:
18 2 2 1
output:
117 1
result:
ok 2 number(s): "117 1"
Test #20:
score: 10
Accepted
time: 174ms
memory: 19328kb
input:
30 2 9 1
output:
264 84
result:
ok 2 number(s): "264 84"
Test #21:
score: 10
Accepted
time: 160ms
memory: 19000kb
input:
29 2 9 1
output:
253 36
result:
ok 2 number(s): "253 36"
Test #22:
score: 10
Accepted
time: 24ms
memory: 14996kb
input:
25 2 8 1
output:
195 8
result:
ok 2 number(s): "195 8"
Subtask #5:
score: 24
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #23:
score: 24
Accepted
time: 819ms
memory: 17212kb
input:
30 4 10 9 5 1
output:
188 40
result:
ok 2 number(s): "188 40"
Test #24:
score: 24
Accepted
time: 1791ms
memory: 17056kb
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: 24
Accepted
time: 1511ms
memory: 19164kb
input:
30 8 10 9 8 7 4 3 2 1
output:
154 1
result:
ok 2 number(s): "154 1"
Test #26:
score: 24
Accepted
time: 1503ms
memory: 17172kb
input:
30 8 10 8 7 6 5 4 3 1
output:
155 1
result:
ok 2 number(s): "155 1"
Test #27:
score: 24
Accepted
time: 1107ms
memory: 19260kb
input:
30 6 10 8 6 4 3 1
output:
150 4
result:
ok 2 number(s): "150 4"
Test #28:
score: 24
Accepted
time: 1884ms
memory: 17148kb
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: 24
Accepted
time: 860ms
memory: 17336kb
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