Submission #202244

#	Time	Username	Problem	Language	Result	Execution time	Memory
202244		ZwariowanyMarcin	Chessboard (IZhO18_chessboard)	C++14	100 / 100	873 ms	4352 KiB

chessboard

#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl

using namespace std;

const int nax = 1e5 + 11;
const LL INF = 1e18;

int n, k;
LL best = INF;

struct pt {
	int x, y, xx, yy;
};

pt t[nax];
		
LL rec(int bok, int x, int y) {
	LL X = x / bok;
	LL Y = y / bok;
	LL black = 0;
	if (X % 2 == 0 || Y % 2 == 0) {
		black += (LL) X * Y / 2 * bok * bok;
	}
	else {
		black += (LL) ((X * Y) / 2 + 1) * bok * bok;
	}
	if (X % 2 == Y % 2) {
		black += (LL) (x - X * bok) * (y - Y * bok);
	}
	if (Y % 2 == 0) {
		black += (LL) (X + 1) / 2 * (y - Y * bok) * bok;
	}
	else {
		black += (LL) X / 2 * (y - Y * bok) * bok;
	}
	if (X % 2 == 0) {
		black += (LL) (Y + 1) / 2 * (x - X * bok) * bok;
	}
	else {
		black += (LL) Y / 2 * (x - X * bok) * bok;
	}
	return black;
}												
	
void solve(int bok) {
	LL sum = 0;
	LL pole = 0;
	for (int i = 0; i < k; ++i) {
		sum += rec(bok, t[i].xx, t[i].yy) - rec(bok, t[i].x - 1, t[i].yy) - rec(bok, t[i].xx, t[i].y - 1) + rec(bok, t[i].x - 1, t[i].y - 1);
		pole += (LL) (t[i].xx - t[i].x + 1) * (t[i].yy - t[i].y + 1);
	}
	LL black = rec(bok, n, n);
	LL white = (LL) n * n - black;
	/*if (bok == 2) {
		cat(rec(2, t[0].x - 1, t[0].yy));
		cat(black);
		cat(white);
		cat(sum);
		cat(pole);
	}
	*/
	best = min(best, (black - sum) + (pole - sum));
	best = min(best, (white - (pole - sum)) + sum);
}
	

int main() {		
	scanf ("%d%d", &n, &k);
	for (int i = 0; i < k; ++i) 
		scanf ("%d %d %d %d", &t[i].x, &t[i].y, &t[i].xx, &t[i].yy);
		
	for (int i = 1; i < n; ++i)
		if (n % i == 0) solve(i);
		
	printf ("%lld", best);
	
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &k);
  ~~~~~~^~~~~~~~~~~~~~~~
chessboard.cpp:77:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d %d", &t[i].x, &t[i].y, &t[i].xx, &t[i].yy);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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