QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#303475#7688. Alea Iacta EstzhouhuanyiWA 142ms16416kbC++142.4kb2024-01-12 16:35:402024-01-12 16:35:40

Judging History

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

  • [2024-01-12 16:35:40]
  • 评测
  • 测评结果:WA
  • 用时:142ms
  • 内存:16416kb
  • [2024-01-12 16:35:40]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 1000000
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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 11724kb

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: 13ms
memory: 12416kb

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: 9ms
memory: 11548kb

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: 13ms
memory: 12376kb

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: 10ms
memory: 12068kb

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: 7ms
memory: 14416kb

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: -100
Wrong Answer
time: 142ms
memory: 16416kb

input:

1
999983 999983

output:

999983 500005 500005 500006 500006 500007 500007 500008 500008 500009 500009 500010 500010 500011 500011 500012 500012 500013 500013 500014 500014 500015 500015 500016 500016 500017 500017 500018 500018 500019 500019 500020 500020 500021 500021 500022 500022 500023 500023 500024 500024 500025 500025...

result:

wrong answer Wrong construction. Different distribution (test case 1)