CF1004D Sonya and Matrix

不要想当然。

考虑到我们一定有存在个数为\(4\)的倍数的数。

否则第一个不是的数即为\(x\)。

那么我们设\(b\)为所有的数的最大值。

那么显然有\(|n - x| + |m - y| = b\)

那么有\(y = n + m - x - b\)

所以我们只要暴力枚举\(t\)的约数，然后暴力判断。

#include<iostream>

#include<cstdio>

#define ll long long

#define N 1000010

ll cnt[N << 1],ct[N << 1];

ll a,b,x,y;

ll t;

ll abs(ll x){return x > 0 ? x : -x;}

int main(){

	scanf("%lld",&t);

	for(int i = 1;i <= t;++i){

		ll x;

		scanf("%lld",&x);

		cnt[x] ++ ;

		b = std::max(x,b);

	}

	for(int i = 1;i <= t;++i){

		if(cnt[i] < i * 4){

			x = i;

			break;

		}

	}

	for(int i = 1;i <= t;++i){

		if(t % i == 0){

			int n,m;

			n = i,m = t / i;

			y = n + m - x - b;

			if(abs(n - x) + abs(m - y) == b){

				for(int i = 1;i <= t;++i)

				ct[i] = 0;

				for(int j = 1;j <= n;++j)

				for(int k = 1;k <= m;++k)

				ct[abs(j - x) + abs(k - y)] ++ ;

				bool k = 1;

				for(int i = 1;i <= t;++i)

				if(cnt[i] != ct[i])

				{

					k = 0;

					break;

				}

				if(k){

					std::cout<<n<<" "<<m<<std::endl<<x<<" "<<y<<std::endl;

					return 0;

				}

			}

		}

	}

	puts("-1");

	return 0;

}

巴特西

CF1004D Sonya and Matrix

最新文章

热门文章