QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404090#8228. 排序flying100 ✓3181ms77572kbC++141.7kb2024-05-03 11:32:462024-05-03 11:32:47

Judging History

This is the latest submission verdict.

  • [2024-05-03 11:32:47]
  • Judged
  • Verdict: 100
  • Time: 3181ms
  • Memory: 77572kb
  • [2024-05-03 11:32:46]
  • Submitted

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