80pts WA 求助
查看原帖
80pts WA 求助
700097
Windless_Wilds楼主2022/4/4 16:06
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define rg register

using namespace std;
il ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch))
    {
        if (ch=='-') f*=-1;
        ch=getchar();
    }
    while (isdigit(ch))
    {
        x=(x<<3)+(x<<1);
        x+=ch-'0';
        ch=getchar();
    }
    return x*f;
}
ll n,a[20],kp[5][5],rowsum[5],colsum[5],lurd=0,ruld=0,sum=0;
bool used[20],flag=0;
il void print()
{
    flag=1;
    cout<<sum<<endl;
    for (rg ll i=1;i<=n;++i)
    {
        for (rg ll j=1;j<=n;++j)
        {
            cout<<kp[i][j]<<' ';
        }
        cout<<endl;
    }
    exit(0);
}
il void dfs(ll x,ll y)
{
    if (flag) return;
    
    if (y==n&&rowsum[x]!=sum) return;
    if (x==n&&colsum[y]!=sum) return;
    if (x==n&&y==1&&ruld!=sum) return;
    if (x==n&&y==n)
    {
        if (x==y&&lurd!=sum) return;
        print();
        return;
    }
    ll nex=x,ney=y+1;
    if (y==n) nex++,ney=1;
    for (rg ll i=1;i<=n*n;++i)
    {
        if (used[i]) continue;
        if (nex==ney) lurd+=a[i];
        if (nex+ney==n+1) ruld+=a[i];
        rowsum[nex]+=a[i];
        colsum[ney]+=a[i];
        used[i]=1;
        kp[nex][ney]=a[i];
        dfs(nex,ney);
        if (flag) return;
        if (nex==ney) lurd-=a[i];
        if (nex+ney==n+1) ruld-=a[i];
        rowsum[nex]-=a[i];
        colsum[ney]-=a[i];
        used[i]=0;
    }
}
int main()
{
    n=read();
    for (rg ll i=1;i<=n*n;++i)
    {
        a[i]=read();
        sum+=a[i];
    }
    sum/=n;
    sort(a+1,a+n*n+1);
    dfs(1,0);
    return 0;
}
2022/4/4 16:06
加载中...