Submission #498764

#	Time	Username	Problem	Language	Result	Execution time	Memory
498764		sireanu_vlad	Chessboard (IZhO18_chessboard)	C++14	8 / 100	2 ms	588 KiB

chessboard

#include <iostream>
using namespace std;

long long n, k, t, x;
bool v[10001][10001];

void f()
{
	x = n*n/2;
	for(int i = n/2; i >= 1; --i)
		if(n % i == 0)
			x = min(x, i*i*((n/i)*(n/i)/2));
	cout << x;
}

bool isprime(long long x)
{
	if(x < 2) return 0;
	if(x == 2 || x == 3) return 1;
	if(x % 2 == 0 || x % 3 == 0) return 0;
	for(int i = 5; i * i <= n; i += 6)
		if(x % i == 0 || x % (i+2) == 0)
			return 0;
	return 1;
}

void read()
{
	cin >> n >> k;
	if(k == 0)
	{
		f();
		return;
	}
	else if(isprime(n))
	{
		cout << n*n/2;
		k = 0;
		return;
	}
	int a, b, c, d;
	for(int i = 0; i < k; ++i)
	{
		cin >> a >> b >> c >> d;
		for(int j = a; j <= c; ++j)
			for(int l = b; l <= d; ++l)
				v[j][l] = 1;
	}
}

void setZero(int I, int J, int l)
{
	for(int i = I; i < I+l; ++i)
		for(int j = J; j < J+l; ++j)
			if(v[i][j]) t++;
}

void setOne(int I, int J, int l)
{
	for(int i = I; i < I+l; ++i)
		for(int j = J; j < J+l; ++j)
			if(!v[i][j]) t++;
}

int v1(int l)
{
	t = 0;
	for(int i = 1; i <= n; i += l)
		for(int j = 1; j <= n; j += l)
		{
			if((i-j) % (2*l))
				setOne(i, j, l);
			else setZero(i, j, l);
		}
	return t;
}

int v2(int l)
{
	t = 0;
	for(int i = 1; i <= n; i += l)
		for(int j = 1; j <= n; j += l)
		{
			if((i-j) % (2*l))
				setZero(i, j, l);
			else setOne(i, j, l);
		}
	return t;
}

void chess()
{
	int pmin = 2e9;
	for(int l = 1; l <= n/2; ++l)
		pmin = min(pmin, min(v1(l), v2(l)));
	cout << pmin;
}

void afis()
{
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
			cout << v[i][j] << ' ';
		cout << '\n';
	}
}

int main()
{
	read();
	if(k != 0) chess();
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30