Submission #65166

#	Time	Username	Problem	Language	Result	Execution time	Memory
65166		kingpig9	Chessboard (IZhO18_chessboard)	C++11	47 / 100	2070 ms	51820 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))

template<class T>
void setmin (T &a, T b) {
	if (b < a) {
		a = b;
	}
}

ll N, K, D;
ll X1[MAXN], X2[MAXN], Y1[MAXN], Y2[MAXN];

ll delta (ll xmx, ll ymx) {
	if (xmx == 0 || ymx == 0) {
		return 0;
	}
	debug("xmx = %lld, ymx = %lld\n", xmx, ymx);

	//which one is covered?
	ll xbound = xmx / D, ybound = ymx / D;
	//0 <= x <= xbound, 0 <= y <= ybound -- how many ways x + y is even?
	ll xeven = (xbound + 1) / 2, yeven = (ybound + 1) / 2, xodd = xbound - xeven, yodd = ybound - yeven;
	debug("xeven = %lld, yeven = %lld. xodd = %lld, yodd = %lld.\n", xeven, yeven, xodd, yodd);
	ll ans = (xeven * yeven + xodd * yodd) * D * D;
	debug("ans start out %lld\n", ans);
	
	ll xlen = xmx - xbound * D, ylen = ymx - ybound * D;

	debug("xbound = %lld, ybound = %lld\n", xbound, ybound);
	if (xlen) {
		//one
		//0 <= y < ybound * D
		if (xbound % 2 == 0) {
			//starts with white
			ans += ((ybound + 1) / 2) * (D * xlen);
		} else {
			//starts with black
			ans += (ybound / 2) * (D * xlen);
		}

		//both
		if (ylen) {
			if ((xbound + ybound) % 2 == 0) {
				ans += xlen * ylen;
			}
		}
	}

	if (ylen) {
		if (ybound % 2 == 0) {
			ans += ((xbound + 1) / 2) * (D * ylen);
		} else {
			ans += (xbound / 2) * (D * ylen);
		}
	}

	debug("CHG %lld\n", ans);
	return ans;
}

#warning int overflow!
ll go() {
	debug("----------D = %lld--------------\n", D);
	ll ans = (N / D) * (N / D) / 2 * D * D;
	debug("ANS ASAS %lld\n", ans);
	for (ll i = 0; i < K; i++) {
		ll area = (X2[i] - X1[i]) * (Y2[i] - Y1[i]);
		ll nchange = delta(X1[i], Y1[i]) + delta(X2[i], Y2[i]) - delta(X1[i], Y2[i]) - delta(X2[i], Y1[i]);
		debug("nchange = %lld\n", nchange);
		ans -= (area - nchange);
		ans += nchange;
	}
	debug("D = %lld, we change %lld\n", D, ans);
	return min(ll(N) * N - ans, ans);
}

int main() {
	scanf("%lld %lld", &N, &K);
	for (ll i = 0; i < K; i++) {
		scanf("%lld %lld %lld %lld", &X1[i], &Y1[i], &X2[i], &Y2[i]);
		X1[i]--;
		Y1[i]--;
	}

	ll ans = ll(N) * N;
	for (D = 1; D < N; D++) {
		if (N % D == 0) {
			setmin(ans, go());
		}
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

chessboard.cpp:72:2: warning: #warning int overflow! [-Wcpp]
 #warning int overflow!
  ^~~~~~~
chessboard.cpp: In function 'int main()':
chessboard.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
chessboard.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld %lld", &X1[i], &Y1[i], &X2[i], &Y2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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