CF632F Magic Matrix

Magic Matrix

鸣谢

。。。201910131627798让我知道了最基础的bitset

代码(分析尽在其中)

/*
    对于一二条件,可以分别在

O(n)O(n^2)的范围求出,对于条

件三,可以先转化为

a[i][j]<=max(a[i][k],b[j][k])

    即为判断是否第i,j行有同时

小于a[i][j]的数.可以先把a[i][j]

从小到大排序,记录每一行出现的数

有哪些,只要用bitset存一下,判断

f[i],f[j]没有同时出现过的位即可
*/
#include<bits/stdc++.h>

using namespace std;

const int N=2600;

int n,cnt;
int a[N][N];

struct nkl
{
    int val,x,y;
}s[N*N];

bitset<N>f[N];

inline bool god(nkl xx,nkl yy)
{
    return xx.val<yy.val;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);

    for (int i=1;i<=n;i++)
        if(a[i][i])
        {
            puts("NOT MAGIC");
            return 0;
        }

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if(a[i][j]!=a[j][i])
            {
                puts("NOT MAGIC");
                return 0;
            }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            s[++cnt].x=i;
            s[cnt].y=j;
            s[cnt].val=a[i][j];
        }sort(s+1,s+cnt+1,god);

    for (int i=1,r;i<=cnt;i=r)
    {
        r=i;
        while(r<=cnt&&s[i].val==s[r].val) r++;
        for (int j=i;j<r;j++)
            if((f[s[j].x]&f[s[j].y]).any())
            {
                puts("NOT MAGIC");
                return 0;
            }

        for (int j=i;j<r;j++)
            f[s[j].x][s[j].y]=1;
    }

    puts("MAGIC");

    return 0;
}