QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303476#7688. Alea Iacta EstzhouhuanyiWA 156ms35736kbC++142.4kb2024-01-12 16:37:522024-01-12 16:37:53

Judging History

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

  • [2024-01-12 16:37:53]
  • 评测
  • 测评结果:WA
  • 用时:156ms
  • 内存:35736kb
  • [2024-01-12 16:37:52]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 3000000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int gcd(int x,int y)
{
	if (!y) return x;
	return gcd(y,x%y);
}
int T,n,m,v[N+1],tong[N+1],tong2[N+1],length,length2;
bool nprime[N+1];
long long res,ans;
int main()
{
	int rt,x,y,d;
	v[1]=1;
	for (int i=2;i<=N;++i)
		if (!nprime[i])
		{
			v[i]=i;
			for (int j=(i<<1);j<=N;j+=i)
			{
				nprime[j]=1;
				if (!v[j]) v[j]=i;
			}
		}
	T=read();
	while (T--)
	{
		n=read(),m=read(),res=1ll*n*m,ans=n+m+min(n,m),rt=length=length2=0;
		for (int i=1;1ll*i*i<=res;++i)
			if (i!=n&&i!=m&&res%i==0&&i+res/i<ans)
				ans=i+res/i,rt=i;
		if (rt)
		{
			x=gcd(rt,n),y=rt/x,length=length2=0;
			for (int i=0;i<x;++i)
				for (int j=0;j<y;++j)
					tong[++length]=i+j+1;
			for (int i=0;i<n/x;++i)
				for (int j=0;j<m/y;++j)
					tong2[++length2]=x*i+y*j+1;
			printf("%d ",length);
			for (int i=1;i<=length;++i) printf("%d ",tong[i]);
			puts("");
			printf("%d ",length2);
			for (int i=1;i<=length2;++i) printf("%d ",tong2[i]);
			puts("");
		}
		else
		{
			d=v[gcd(n,m)],length=length2=0;
			if (d!=1&&(d!=n||d!=m))
			{
				for (int i=0;i<n/d;++i)
					for (int j=0;j<d;++j)
						tong[++length]=i*d+j*(m/d)+1;
				for (int i=0;i<m/d;++i)
					for (int j=0;j<d;++j)
						tong2[++length2]=i+j+1;
				printf("%d ",length);
				for (int i=1;i<=length;++i) printf("%d ",tong[i]);
				puts("");
				printf("%d ",length2);
				for (int i=1;i<=length2;++i) printf("%d ",tong2[i]);
				puts("");
			}
			else if (n<m)
			{
				for (int i=0;i<n;++i) tong[++length]=i+1,tong[++length]=i+1;
				for (int i=0;i<m;++i) tong2[++length2]=i+1;
				printf("%d ",length);
				for (int i=1;i<=length;++i) printf("%d ",tong[i]);
				puts("");
				printf("%d ",length2);
				for (int i=1;i<=length2;++i) printf("%d ",tong2[i]);
				puts("");
			}
			else
			{
				for (int i=0;i<n;++i) tong[++length]=i+1;
				for (int i=0;i<m;++i) tong2[++length2]=i+1,tong2[++length2]=i+1;
				printf("%d ",length);
				for (int i=1;i<=length;++i) printf("%d ",tong[i]);
				puts("");
				printf("%d ",length2);
				for (int i=1;i<=length2;++i) printf("%d ",tong2[i]);
				puts("");
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 34ms
memory: 23272kb

input:

3
2 8
1 9
2 9

output:

4 1 2 2 3 
4 1 3 5 7 
3 1 2 3 
3 1 4 7 
3 1 2 3 
6 1 4 7 2 5 8 

result:

ok Correct. (3 test cases)

Test #2:

score: 0
Accepted
time: 47ms
memory: 23280kb

input:

1
40013 40013

output:

40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 33ms
memory: 23280kb

input:

1
40013 1

output:

40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #4:

score: 0
Accepted
time: 28ms
memory: 21220kb

input:

1
2 40013

output:

4 1 1 2 2 
40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

result:

ok Correct. (1 test case)

Test #5:

score: 0
Accepted
time: 33ms
memory: 23288kb

input:

1
3 40013

output:

6 1 1 2 2 3 3 
40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 ...

result:

ok Correct. (1 test case)

Test #6:

score: 0
Accepted
time: 32ms
memory: 23448kb

input:

1
4 40013

output:

8 1 1 2 2 3 3 4 4 
40013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95...

result:

ok Correct. (1 test case)

Test #7:

score: 0
Accepted
time: 156ms
memory: 35736kb

input:

1
999983 999983

output:

999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #8:

score: 0
Accepted
time: 84ms
memory: 25332kb

input:

1
1 999983

output:

2 1 1 
999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

result:

ok Correct. (1 test case)

Test #9:

score: 0
Accepted
time: 75ms
memory: 27364kb

input:

1
2 999983

output:

4 1 1 2 2 
999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

result:

ok Correct. (1 test case)

Test #10:

score: 0
Accepted
time: 77ms
memory: 27312kb

input:

1
999983 3

output:

999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #11:

score: 0
Accepted
time: 70ms
memory: 27380kb

input:

1
999983 4

output:

999983 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #12:

score: -100
Wrong Answer
time: 120ms
memory: 31464kb

input:

1
1000000 1000000

output:

800000 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 5 6 7 8 6 7 8 9 7 8 9 10 8 9 10 11 9 10 11 12 10 11 12 13 11 12 13 14 12 13 14 15 13 14 15 16 14 15 16 17 15 16 17 18 16 17 18 19 17 18 19 20 18 19 20 21 19 20 21 22 20 21 22 23 21 22 23 24 22 23 24 25 23 24 25 26 24 25 26 27 25 26 27 28 26 27 28 29 27 28 29 30...

result:

wrong answer Jury has a better answer. (test case 1)