QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #461013 | #8485. Magic Square | Lynkcat# | WA | 0ms | 3848kb | C++14 | 4.2kb | 2024-07-02 15:07:00 | 2024-07-02 15:07:00 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N
using namespace std;
const int N=1005;
int n,a[N][N],f[N],g[N];
void BellaKira()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cin>>a[i][j],f[i]+=a[i][j],g[j]+=a[i][j];
if (n<=4)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int x=1;x<=n;x++)
for (int y=1;y<=n;y++)
if (i!=x||j!=y)
{
f[i]-=a[i][j],g[j]-=a[i][j];
f[x]-=a[x][y],g[y]-=a[x][y];
swap(a[i][j],a[x][y]);
f[i]+=a[i][j],g[j]+=a[i][j];
f[x]+=a[x][y],g[y]+=a[x][y];
bool bl=1;
for (int k=1;k<=n;k++) bl&=(f[k]==f[1]&&g[k]==f[1]);
if (!bl)
{
f[i]-=a[i][j],g[j]-=a[i][j];
f[x]-=a[x][y],g[y]-=a[x][y];
swap(a[i][j],a[x][y]);
f[i]+=a[i][j],g[j]+=a[i][j];
f[x]+=a[x][y],g[y]+=a[x][y];
continue;
}
cout<<i<<" "<<j<<" "<<x<<" "<<y<<'\n';
return;
}
return;
}
map<int,int>Mp;
for (int i=1;i<=n;i++) Mp[f[i]]++,Mp[g[i]]++;
int p=0;
for (auto [u,v]:Mp)
if (v>Mp[p])
{
p=u;
}
poly gx,gy;
for (int i=1;i<=n;i++)
if (f[i]!=p) gx.push_back(i);
for (int i=1;i<=n;i++)
if (g[i]!=p) gy.push_back(i);
// for (auto u:gx) cout<<u<<",";cout<<endl;
// for (auto u:gy) cout<<u<<",";cout<<endl;
int tot=0;
for (int i=1;i<=n;i++) tot+=f[i]!=p,tot+=g[i]!=p;
if (tot==0)
{
cout<<1<<" "<<1<<" "<<n<<" "<<n<<'\n';
return;
}
if (sz(gx)==0) for (int i=1;i<=n;i++) gx.push_back(i);
if (sz(gy)==0) for (int i=1;i<=n;i++) gy.push_back(i);
for (int i:gx)
for (int j:gy)
for (int x:gx)
for (int y:gy)
if (i!=x||j!=y)
{
tot-=(f[i]==p);tot-=(g[j]==p);
if (x!=i) tot-=(f[x]==p);
if (y!=j) tot-=(g[y]==p);
f[i]-=a[i][j],g[j]-=a[i][j];
f[x]-=a[x][y],g[y]-=a[x][y];
swap(a[i][j],a[x][y]);
f[i]+=a[i][j],g[j]+=a[i][j];
f[x]+=a[x][y],g[y]+=a[x][y];
tot+=(f[i]==p);tot+=(g[j]==p);
if (x!=i) tot+=(f[x]==p);
if (y!=j) tot+=(g[y]==p);
if (tot!=0)
{
tot-=(f[i]==p);tot-=(g[j]==p);
if (x!=i) tot-=(f[x]==p);
if (y!=j) tot-=(g[y]==p);
f[i]-=a[i][j],g[j]-=a[i][j];
f[x]-=a[x][y],g[y]-=a[x][y];
swap(a[i][j],a[x][y]);
f[i]+=a[i][j],g[j]+=a[i][j];
f[x]+=a[x][y],g[y]+=a[x][y];
tot+=(f[i]==p);tot+=(g[j]==p);
if (x!=i) tot+=(f[x]==p);
if (y!=j) tot+=(g[y]==p);
continue;
}
cout<<i<<" "<<j<<" "<<x<<" "<<y<<'\n';
return;
}
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
3 6 9 2 3 5 7 8 1 4
output:
1 1 3 3
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
4 16 3 2 13 5 10 11 8 9 6 7 12 1 15 14 4
output:
2 1 2 4
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
3 8 1 6 3 5 7 4 2 9
output:
3 2 3 3
result:
ok OK
Test #4:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
4 9 12 7 6 4 2 14 15 16 13 1 3 5 8 11 10
output:
2 2 3 3
result:
ok OK
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3652kb
input:
5 15 17 1 8 24 3 10 19 21 12 16 23 7 14 6 22 4 13 20 5 9 11 25 2 18
output:
3 1 3 2
result:
wrong answer Incorrect sum in row 1