42D - Strange town - CodeForces Solution

// Problem: Strange town
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF42D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=25,BS=1005;

int n,m,val[S],vis[BS];

inline bool check(int x)
{
	val[x]=m;
	for(int i=0;i<=BS-3;i++) vis[i]=false;
	for(int i=1;i<=x;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(vis[val[i]+val[j]]) return false;
			vis[val[i]+val[j]]=true;
		}
	}
	return true;
}

int main()
{
	scanf("%d",&n);
	val[1]=0,val[2]=1;
	m=2;
	for(int i=3;i<=n;i++)
	{
		while(!check(i)) m++;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			printf("%d ",i==j?0:val[i]+val[j]);
		}
		printf("\n");
	}
	return 0;
}