QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303471#7688. Alea Iacta EstzhouhuanyiWA 13ms12124kbC++142.4kb2024-01-12 16:26:092024-01-12 16:26:09

Judging History

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

  • [2024-01-12 16:26:09]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:12124kb
  • [2024-01-12 16:26:09]
  • 提交

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=inf,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
			{
				printf("%d\n",n+(m<<1));
				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: 12ms
memory: 11716kb

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

input:

1
40013 40013

output:

120039
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...

result:

wrong answer Integer parameter [name=ai] equals to 80026, violates the range [1, 80025] (test case 1)