QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303721 | #7688. Alea Iacta Est | zhouhuanyi | WA | 2ms | 12112kb | C++14 | 2.5kb | 2024-01-12 22:14:37 | 2024-01-12 22:14:38 |
Judging History
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)