632F - Magic Matrix - CodeForces Solution

#include<iostream>
#include<bitset>
#include<algorithm>
using namespace std;
#define N 2510
int n,a[N][N],cnt;
bitset<N> b[N];
struct node
{
	int w,x,y;
	friend bool operator<(node a,node b)
	{
		return a.w>b.w;
	}
}f[N*N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		cin>>a[i][j];
		f[++cnt]=(node){a[i][j],i,j};
	}
	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;
		}
		if(i==j&&a[i][j])
		{
			puts("NOT MAGIC");
			return 0;
		}
	}
	sort(f+1,f+cnt+1);
	int now=0;
	while(now<cnt)
	{
		now++;
		int tmp=now;
		b[f[now].x].set(f[now].y);
		while(now<cnt&&f[now+1].w==f[now].w)
		{
			now++;
			b[f[now].x].set(f[now].y);
		}
		if(now==cnt)
		 break;
		for(int i=tmp;i<=now;i++)
		{
			int x=f[i].x,y=f[i].y;
			if((b[x]|b[y]).count()!=n)
			{
//				cout<<x<<" "<<y<<":"<<(b[x]|b[y]).count()<<endl;
				puts("NOT MAGIC");
				return 0;
			}
		}
	}
	puts("MAGIC");
}