QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303475 | #7688. Alea Iacta Est | zhouhuanyi | WA | 142ms | 16416kb | C++14 | 2.4kb | 2024-01-12 16:35:40 | 2024-01-12 16:35:40 |
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=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;
}
Details
Tip: Click on the bar to expand more detailed information
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)