oj.uz

Submission #498764

# Submission time Handle Problem Language Result Execution time Memory
498764 2021-12-26T10:10:03 Z sireanu_vlad Chessboard (IZhO18_chessboard) C++14
8 / 100
 2 ms 588 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 0 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -