QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303721#7688. Alea Iacta EstzhouhuanyiWA 2ms12112kbC++142.5kb2024-01-12 22:14:372024-01-12 22:14:38

Judging History

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

  • [2024-01-12 22:14:38]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12112kb
  • [2024-01-12 22:14:37]
  • 提交

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],F[N+1],st[N+1],st2[N+1],tong[N+1],tong2[N+1],leng,leng2,length,length2;
bool nprime[N+1];
long long res,ans;
bool check(int x,int y,int z)
{
	for (int i=0;i<y;++i)
		if (1ll*x*i<=z&&(z-x*i)%y==0)
			return 1;
	return 0;
}
int main()
{
	int rt,x,y,a,b,c,d,e;
	T=read();
	while (T--)
	{
		x=n=read(),y=m=read(),res=1ll*n*m,ans=n+m+min(n,m),rt=a=b=c=d=e=leng=leng2=length=length2=0;
		for (int i=2;i<=n;++i)
			while (x%i==0)
				st[++leng]=i,x/=i;
		for (int i=2;i<=m;++i)
			while (y%i==0)
				st2[++leng2]=i,y/=i;
		for (int i=1;i<=leng;++i)
			for (int j=i+1;j<=leng;++j)
				if (check(st[i],st[j],m))
					ans=n+m,a=st[i],b=st[j],c=n/a/b,d=a*b,e=m;
		for (int i=1;i<=leng2;++i)
			for (int j=i+1;j<=leng2;++j)
				if (check(st2[i],st2[j],n))
					ans=n+m,a=st2[i],b=st2[j],c=m/a/b,d=a*b,e=n;
		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;
			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;
		}
		else if (a)
		{
			for (int i=0;i<a;++i)
				for (int j=0;j<b;++j)
					for (int k=0;k<c;++k)
						tong[++length]=i+j+k*(a*b)+1;
			for (int i=0;i<=n+m;++i) F[i]=0;
			F[0]=1,F[d]=-1,F[e]-=1,F[d+e]=1;
			for (int i=a;i<=n+m;++i) F[i]+=F[i-a];
			for (int i=b;i<=n+m;++i) F[i]+=F[i-b];
			for (int i=0;i<=n+m;++i)
				for (int j=1;j<=F[i];++j)
					tong2[++length2]=i+1;
		}
		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;
			}
			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 %d\n",length,length2);
		for (int i=1;i<=length;++i) printf("%d ",tong[i]);
		puts("");
		for (int i=1;i<=length2;++i) printf("%d ",tong2[i]);
		puts("");
		/*
		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: 0
Wrong Answer
time: 2ms
memory: 12112kb

input:

3
2 8
1 9
2 9

output:

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

result:

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