QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#404090 | #8228. 排序 | flying | 100 ✓ | 3181ms | 77572kb | C++14 | 1.7kb | 2024-05-03 11:32:46 | 2024-05-03 11:32:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
const int N=(1<<20)+5;
int d[15], trans[N][15], n, m;
int state[N], cnt;
pair <int,int> dp[N];
void upd(pair<int,int>& x,pair<int,int> y)
{
if(x.first<y.first)
x=y;
else if(x.first==y.first)
{
x.second += y.second;
if(x.second>=Mod)
x.second -= Mod;
}
}
int calctrans(int S,int id)
{
int newS=0;
for(int i=0;i<d[id];i++)
{
int cnt=0;
for(int j=i;j<n;j+=d[id])
cnt += (S>>j)&1;
for(int j=i;j<n;j+=d[id])
{
cnt--;
if(cnt>=0)
newS += 1<<j;
}
}
return newS;
}
int calc(int id1,int id2)
{
int S1=state[id1], S2=state[id2], ans=0;
for(int i=1;i<=m;i++)
{
int p=round(log2(S2-S1));
for(int j=p;j<n;j+=d[i])
if((S1>>j)&1)
ans++;
S1=trans[id1][i], S2=trans[id2][i];
}
return ans;
}
void dfs(int x,int S)
{
if(x==d[1])
{
state[++cnt]=S;
return;
}
for(int i=x;i<n;i+=d[1])
S += 1<<i;
dfs(x+1,S);
for(int i=x;i<n;i+=d[1])
{
S -= 1<<i;
dfs(x+1,S);
}
}
int getid(int x)
{
return lower_bound(state+1,state+cnt+1,x)-state;
}
int main()
{
cin >> n >> m;
for(int i=1;i<=m;i++)
scanf("%d",&d[i]);
dfs(0,0);
sort(state+1,state+cnt+1);
for(int i=1;i<=cnt;i++)
{
trans[i][0]=state[i];
for(int j=1;j<=m;j++)
trans[i][j]=calctrans(trans[i][j-1],j);
}
dp[1]=make_pair(0,1);
for(int i=1;i<cnt;i++)
{
int S=state[i];
for(int j=0;j<n;j++)
if(((S>>j)&1)==0 && (j+d[1]>=n || (S>>(j+d[1]))&1))
{
int newid=getid(S+(1<<j));
upd(dp[newid],make_pair(dp[i].first+calc(i,newid),dp[i].second));
}
}
printf("%d %d\n",dp[cnt].first,dp[cnt].second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 18
Accepted
Test #1:
score: 18
Accepted
time: 0ms
memory: 3760kb
input:
2 2 2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 18
Accepted
time: 1ms
memory: 3828kb
input:
5 4 5 4 2 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #3:
score: 18
Accepted
time: 1ms
memory: 3780kb
input:
8 4 6 3 2 1
output:
15 4
result:
ok 2 number(s): "15 4"
Test #4:
score: 18
Accepted
time: 1ms
memory: 3960kb
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: 1ms
memory: 3912kb
input:
8 3 8 7 1
output:
22 7
result:
ok 2 number(s): "22 7"
Test #6:
score: 18
Accepted
time: 1ms
memory: 3856kb
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: 0ms
memory: 3948kb
input:
16 2 6 1
output:
77 15
result:
ok 2 number(s): "77 15"
Test #8:
score: 27
Accepted
time: 17ms
memory: 4768kb
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: 25ms
memory: 4756kb
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: 20ms
memory: 4720kb
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: 5ms
memory: 4040kb
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: 2ms
memory: 4268kb
input:
22 3 5 3 1
output:
100 1
result:
ok 2 number(s): "100 1"
Test #13:
score: 21
Accepted
time: 1ms
memory: 3860kb
input:
22 1 1
output:
231 1
result:
ok 2 number(s): "231 1"
Test #14:
score: 21
Accepted
time: 148ms
memory: 11232kb
input:
22 4 10 8 3 1
output:
97 4
result:
ok 2 number(s): "97 4"
Test #15:
score: 21
Accepted
time: 171ms
memory: 11232kb
input:
22 5 10 7 6 3 1
output:
92 70
result:
ok 2 number(s): "92 70"
Test #16:
score: 21
Accepted
time: 186ms
memory: 11336kb
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: 266ms
memory: 11232kb
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: 4ms
memory: 4156kb
input:
14 2 10 1
output:
61 210
result:
ok 2 number(s): "61 210"
Test #19:
score: 10
Accepted
time: 1ms
memory: 3952kb
input:
18 2 2 1
output:
117 1
result:
ok 2 number(s): "117 1"
Test #20:
score: 10
Accepted
time: 572ms
memory: 39836kb
input:
30 2 9 1
output:
264 84
result:
ok 2 number(s): "264 84"
Test #21:
score: 10
Accepted
time: 440ms
memory: 32744kb
input:
29 2 9 1
output:
253 36
result:
ok 2 number(s): "253 36"
Test #22:
score: 10
Accepted
time: 76ms
memory: 9704kb
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: 1746ms
memory: 77500kb
input:
30 4 10 9 5 1
output:
188 40
result:
ok 2 number(s): "188 40"
Test #24:
score: 24
Accepted
time: 2915ms
memory: 77564kb
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: 2774ms
memory: 77572kb
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: 2732ms
memory: 77492kb
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: 2284ms
memory: 77564kb
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: 3181ms
memory: 77488kb
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: 1657ms
memory: 59076kb
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