QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303472 | #7688. Alea Iacta Est | zhouhuanyi | WA | 18ms | 12232kb | C++14 | 2.3kb | 2024-01-12 16:26:58 | 2024-01-12 16:26:59 |
Judging History
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
{
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: 11ms
memory: 12220kb
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: 18ms
memory: 11704kb
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: 13ms
memory: 12068kb
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: -100
Wrong Answer
time: 10ms
memory: 12232kb
input:
1 2 40013
output:
1 1 80026 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 1...
result:
wrong answer Integer parameter [name=m1] equals to 80026, violates the range [1, 40017] (test case 1)