QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #338477 | #7227. The Magic Square | Kevin5307 | WA | 1ms | 3768kb | C++20 | 1.5kb | 2024-02-25 22:35:51 | 2024-02-25 22:35:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int grid[1010][1010];
int main()
{
int n;
cin>>n;
if(n==2||n==3||n==5)
{
cout<<"Impossible"<<endl;
return 0;
}
if(n==8)
{
cout<<"Possible"<<endl;
cout<<"4"<<endl;
cout<<"1 2 3 4"<<endl;
cout<<"5 8 8 8"<<endl;
cout<<"6 8 8 8"<<endl;
cout<<"7 8 8 8"<<endl;
return 0;
}
cout<<"Possible"<<endl;
int a=-1,b=-1;
for(int x=0;x<=100;x++)
for(int y=0;y<=100;y++)
if(n==1+x*3+y*5)
{
a=x;
b=y;
break;
}
vector<array<int,3>> vec;
vec.push_back({1,0,0});
while(a--)
{
sort(vec.rbegin(),vec.rend());
if(vec.back()[0]%2)
for(auto &arr:vec)
arr[0]*=2;
auto arr=vec.back();
vec.pop_back();
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
vec.push_back({arr[0]/2,arr[1]+i*arr[0]/2,arr[2]+j*arr[0]/2});
}
while(b--)
{
sort(vec.rbegin(),vec.rend());
if(vec.back()[0]%2)
for(auto &arr:vec)
arr[0]*=3;
auto arr=vec.back();
vec.pop_back();
for(int i=0;i<3;i++)
for(int j=0;j<3;j++) if(!i||!j)
vec.push_back({arr[0]/3,arr[1]+i*arr[0]/3,arr[2]+j*arr[0]/3});
vec.push_back({arr[0]/3*2,arr[1]+arr[0]/3,arr[2]+arr[0]/3});
}
int cnt=0;
int tot=0;
for(auto arr:vec)
{
tot+=arr[0]*arr[0];
cnt++;
for(int i=0;i<arr[0];i++)
for(int j=0;j<arr[0];j++)
grid[arr[1]+i][arr[2]+j]=cnt;
}
tot=sqrt(tot)+0.1;
cout<<tot<<endl;
for(int i=0;i<tot;i++)
{
for(int j=0;j<tot;j++)
cout<<grid[i][j]<<" ";
cout<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2
output:
Impossible
result:
ok No solution for 2 squares
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
4
output:
Possible 2 1 2 3 4
result:
ok answer 4 squares of 1 different sizes in total 2 * 2
Test #3:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
1
output:
Possible 1 1
result:
ok answer 1 squares of 1 different sizes in total 1 * 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
3
output:
Impossible
result:
ok No solution for 3 squares
Test #5:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
5
output:
Impossible
result:
ok No solution for 5 squares
Test #6:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
6
output:
Possible 3 1 2 3 4 6 6 5 6 6
result:
ok answer 6 squares of 2 different sizes in total 3 * 3
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3560kb
input:
7
output:
Possible 4 4 5 3 0 6 7 3 0 2 2 1 0 0 0 0 0
result:
wrong answer Illegal construction