Submission #65170

#	Time	Username	Problem	Language	Result	Execution time	Memory
65170		kingpig9	Chessboard (IZhO18_chessboard)	C++11	47 / 100	2025 ms	3836 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, D;
ll dsqr;
int K;
ll X1[MAXN], X2[MAXN], Y1[MAXN], Y2[MAXN];
ll totrect;

ll delta (ll xmx, ll ymx) {
	if (xmx == 0 || ymx == 0) {
		return 0;
	}

	//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 xodd = xbound >> 1, yodd = ybound >> 1, xeven = xbound - xodd, yeven = ybound - yodd;
	ll ans = (xeven * yeven + xodd * yodd) * dsqr;
	
	ll xlen = xmx - xbound * D, ylen = ymx - ybound * D;

	if (xlen) {
		//one
		//0 <= y < ybound * D
		ans += ((xbound & 1) ? yodd : yeven) * D * xlen;

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

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

	return ans;
}

ll go() {
	dsqr = D * D;

	ll ans = dsqr * (((N / D) * (N / D)) >> 1) - totrect;
	for (int i = 0; i < K; i++) {
		ans += (delta(X1[i], Y1[i]) + delta(X2[i], Y2[i]) - delta(X1[i], Y2[i]) - delta(X2[i], Y1[i])) << 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:71: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:73: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