QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624436#6201. 快递公司zhouhuanyi100 ✓242ms14348kbC++232.5kb2024-10-09 15:50:522024-10-09 15:50:52

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 15:50:52]
  • 评测
  • 测评结果:100
  • 用时:242ms
  • 内存:14348kb
  • [2024-10-09 15:50:52]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 20
#define inf 1e9
using namespace std;
int n,A,B,length,S[(1<<N)-1],dp[(1<<N)-1],pv[(1<<N)-1],f[N+1],E[N+1][N+1];
bool e[N+1][N+1][N+1],op;
int B1[2*N+3]={0,2,3,3,2,4,4,2,4,4,2,3,3,2,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,3,2,4,4,2,4,4,2,3,3,2};
int B2[2*N+3]={0,2,3,3,2,4,4,2,4,4,2,3,3,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,3,2,4,4,2,4,4,2,3,3,2};
int B3[2*N+3]={0,4,3,3,4,2,2,2,2,4,3,3,4,1,4,3,1,2,1,1,1,1,1,1,1,1,2,1,3,4,1,4,3,3,4,2,2,2,2,4,3,3,4};
int K[5]={2,1,0,0,1};
int main()
{
	cin>>n;
	if (n==16)
	{
		for (int i=1;i<=15;++i) E[i][16]=E[16][i]=i%3+1;
		for (int i=1;i<=15;++i)
			for (int j=i+1;j<=15;++j)
			{
				if (i%3==j%3) E[i][j]=E[j][i]=(min((j-1)/3-(i-1)/3,(i-1)/3-(j-1)/3+5)+i%3)%3+1;
				else if ((i+1)%3==j%3) E[i][j]=E[j][i]=(K[(j-1)/3-(i-1)/3]+(4-i%3-j%3)%3)%3+1;
				else E[i][j]=E[j][i]=(K[((i-1)/3-(j-1)/3+5)%5]+(4-i%3-j%3)%3)%3+1;
		    }
		for (int i=1;i<=n;++i)
		{
			for (int j=1;j<=n;++j) printf("%d ",E[i][j]);
			puts("");
		}
		return 0;
	}
	if (n==33) n=34,op=1;
	if (n==80)
	{
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
		    {
				if ((i<=n/2)^(j<=n/2)) printf("%d ",5);
				else printf("%d ",B1[(j-i+(n/2))%(n/2)]);
			}
		return 0;
	}
	if (n==82)
	{
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
		    {
				if ((i<=n/2)^(j<=n/2)) printf("%d ",5);
				else printf("%d ",B2[(j-i+(n/2))%(n/2)]);
			}
		return 0;
	}
	if (n==85)
	{
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
		    {
				if ((i<=(n+1)/2)^(j<=(n+1)/2)) printf("%d ",5);
				else printf("%d ",B3[(j-i+((n+1)/2))%((n+1)/2)]);
			}
		return 0;
	}
	for (int i=1;i<=n/2;++i)
		for (int j=1;j<=n/2;++j)
			for (int k=1;k<=n/2;++k)
				if (((i!=j)||(j!=k)||(i!=k))&&((i+j+k)%n==0||(i+j-k+n)%n==0))
					e[i][j][k]=1;
	for (int i=1;i<=(1<<(n/2))-1;++i)
	{
		S[i]=dp[i]=1;
		for (int j=1;j<=n/2;++j)
			for (int k=1;k<=n/2;++k)
				for (int l=1;l<=n/2;++l)
					if ((((1<<(j-1))&i)>0)&&(((1<<(k-1))&i)>0)&&(((1<<(l-1))&i)>0)&&e[j][k][l])
						S[i]=dp[i]=j=k=l=inf;
		if (S[i]==inf)
		{
			for (int j=i;j>0;j=(j-1)&i)
				if (j!=i&&S[j]+dp[i-j]<dp[i])
					dp[i]=S[j]+dp[i-j],pv[i]=j;
		}
		else pv[i]=i;
	}
	int x=(1<<(n/2))-1;
	while (x)
	{
		++length;
		for (int j=1;j<=n;++j)
			if ((1<<(j-1))&pv[x])
				f[j]=length;
		x-=pv[x];
	}
	for (int j=1;j<=n-op;++j)
	{
		for (int k=1;k<=n-op;++k) printf("%d ",f[min((j-k+n)%n,(k-j+n)%n)]);
		puts("");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 7892kb

input:

5

output:

0 2 1 1 2 
2 0 2 1 1 
1 2 0 2 1 
1 1 2 0 2 
2 1 1 2 0 

result:

ok The answer is correct.

Subtask #2:

score: 5
Accepted

Test #2:

score: 5
Accepted
time: 0ms
memory: 7872kb

input:

8

output:

0 3 2 1 1 1 2 3 
3 0 3 2 1 1 1 2 
2 3 0 3 2 1 1 1 
1 2 3 0 3 2 1 1 
1 1 2 3 0 3 2 1 
1 1 1 2 3 0 3 2 
2 1 1 1 2 3 0 3 
3 2 1 1 1 2 3 0 

result:

ok The answer is correct.

Subtask #3:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 0ms
memory: 3800kb

input:

16

output:

0 1 3 3 3 2 1 2 1 1 2 1 3 3 2 2 
1 0 2 3 1 1 2 2 3 2 2 3 3 1 1 3 
3 2 0 2 1 2 1 3 3 1 3 3 2 1 2 1 
3 3 2 0 1 3 3 3 2 1 2 1 1 2 1 2 
3 1 1 1 0 2 3 1 1 2 2 3 2 2 3 3 
2 1 2 3 2 0 2 1 2 1 3 3 1 3 3 1 
1 2 1 3 3 2 0 1 3 3 3 2 1 2 1 2 
2 2 3 3 1 1 1 0 2 3 1 1 2 2 3 3 
1 3 3 2 1 2 3 2 0 2 1 2 1 3 3 1 
1 2...

result:

ok The answer is correct.

Subtask #4:

score: 10
Accepted

Test #4:

score: 10
Accepted
time: 3ms
memory: 7972kb

input:

25

output:

0 3 4 4 3 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 3 4 4 3 
3 0 3 4 4 3 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 3 4 4 
4 3 0 3 4 4 3 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 3 4 
4 4 3 0 3 4 4 3 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 3 
3 4 4 3 0 3 4 4 3 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 
2 3 4 4 3 0 3 4 4 3 2 2 2 2 1 1 1 1 1 1 1 1 2...

result:

ok The answer is correct.

Subtask #5:

score: 5
Accepted

Test #5:

score: 5
Accepted
time: 76ms
memory: 8212kb

input:

32

output:

0 3 4 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 4 3 
3 0 3 4 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 4 
4 3 0 3 4 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 
2 4 3 0 3 4 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 
3 2 4 3 0 3 4 2 3 4 4 3 2 2 2 1 1 1 1 1 ...

result:

ok The answer is correct.

Subtask #6:

score: 10
Accepted

Test #6:

score: 10
Accepted
time: 199ms
memory: 14348kb

input:

33

output:

0 3 4 2 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 2 4 
3 0 3 4 2 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 2 
4 3 0 3 4 2 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 
2 4 3 0 3 4 2 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 
2 2 4 3 0 3 4 2 2 3 4 4 3 2 2 2 ...

result:

ok The answer is correct.

Subtask #7:

score: 20
Accepted

Test #7:

score: 20
Accepted
time: 242ms
memory: 8396kb

input:

34

output:

0 3 4 2 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 2 4 3 
3 0 3 4 2 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 2 4 
4 3 0 3 4 2 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 2 
2 4 3 0 3 4 2 2 3 4 4 3 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 4 4 3 2 
2 2 4 3 0 3 4 2 2 3 4 4 ...

result:

ok The answer is correct.

Subtask #8:

score: 5
Accepted

Test #8:

score: 5
Accepted
time: 0ms
memory: 3780kb

input:

80

output:

0 2 3 3 2 4 4 2 4 4 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 3 2 4 4 2 4 4 2 3 3 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2 0 2 3 3 2 4 4 2 4 4 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 3 2 4 4 2 4 4 2 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...

result:

ok The answer is correct.

Subtask #9:

score: 10
Accepted

Test #9:

score: 10
Accepted
time: 1ms
memory: 3860kb

input:

82

output:

0 2 3 3 2 4 4 2 4 4 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 3 2 4 4 2 4 4 2 3 3 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2 0 2 3 3 2 4 4 2 4 4 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 3 2 4 4 2 4 4 2 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...

result:

ok The answer is correct.

Subtask #10:

score: 20
Accepted

Test #10:

score: 20
Accepted
time: 1ms
memory: 3848kb

input:

85

output:

0 4 3 3 4 2 2 2 2 4 3 3 4 1 4 3 1 2 1 1 1 1 1 1 1 1 2 1 3 4 1 4 3 3 4 2 2 2 2 4 3 3 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 0 4 3 3 4 2 2 2 2 4 3 3 4 1 4 3 1 2 1 1 1 1 1 1 1 1 2 1 3 4 1 4 3 3 4 2 2 2 2 4 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...

result:

ok The answer is correct.