Submission #65172

#	Time	Username	Problem	Language	Result	Execution time	Memory
65172		kingpig9	Chessboard (IZhO18_chessboard)	C++11	100 / 100	1332 ms	8944 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))

ll sqr (ll x) {
	return x * x;
}

void setmin (ll &a, ll b) {
	if (b < a) {
		a = b;
	}
}

ll N, D;
ll dsqr;
int K;
ll X1[MAXN], X2[MAXN], Y1[MAXN], Y2[MAXN];
ll xmx[2], ymx[2];
ll xbound[2], ybound[2];
ll xodd[2], yodd[2], xeven[2], yeven[2];
ll xlen[2], ylen[2];
ll totrect;

ll delta (int i, int j) {
	if (xmx[i] == 0 || ymx[j] == 0) {
		return 0ll;
	}

	//which one is covered?
	//0 <= x <= xbound, 0 <= y <= ybound -- how many ways x + y is even?
	ll ans = (xeven[i] * yeven[j] + xodd[i] * yodd[j]) * dsqr;
	
	if (xlen[i]) {
		//one
		//0 <= y < ybound * D
		ans += ((xbound[i] & 1) ? yodd[j] : yeven[j]) * D * xlen[i];

		//both
		if (ylen[j]) {
			if ((xbound[i] & 1) == (ybound[j] & 1)) {
				ans += xlen[i] * ylen[j];
			}
		}
	}

	if (ylen[j]) {
		ans += ((ybound[j] & 1) ? xodd[i] : xeven[i]) * D * ylen[j];
	}

	return ans;
}

ll go() {
	dsqr = sqr(D);
	ll ans = dsqr * (sqr(N / D) >> 1) - totrect;

	for (int i = 0; i < K; i++) {
		xmx[0] = X1[i];
		xmx[1] = X2[i];
		ymx[0] = Y1[i];
		ymx[1] = Y2[i];
		xbound[0] = xmx[0] / D;
		xbound[1] = xmx[1] / D;
		ybound[0] = ymx[0] / D;
		ybound[1] = ymx[1] / D;
		xodd[0] = xbound[0] >> 1;
		xeven[0] = xbound[0] - xodd[0];
		yodd[0] = ybound[0] >> 1;
		yeven[0] = ybound[0] - yodd[0];
		xodd[1] = xbound[1] >> 1;
		xeven[1] = xbound[1] - xodd[1];
		yodd[1] = ybound[1] >> 1;
		yeven[1] = ybound[1] - yodd[1];
		xlen[0] = xmx[0] - xbound[0] * D;
		xlen[1] = xmx[1] - xbound[1] * D;
		ylen[0] = ymx[0] - ybound[0] * D;
		ylen[1] = ymx[1] - ybound[1] * D;

		ans += (delta(0, 0) + delta(1, 1) - delta(0, 1) - delta(1, 0)) << 1;
	}
	return min(N * N - ans, ans);
}

int main() {
	scanf("%lld %d", &N, &K);
	for (int i = 0; i < K; i++) {
		scanf("%lld %lld %lld %lld", &X1[i], &Y1[i], &X2[i], &Y2[i]);
		X1[i]--;
		Y1[i]--;
		totrect += (X2[i] - X1[i]) * (Y2[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: In function 'int main()':
chessboard.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~
chessboard.cpp:97: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: 23 / 23
• Subtask 6: 30 / 30