Submission #872768

#	Time	Username	Problem	Language	Result	Execution time	Memory
872768		epicci23	Chessboard (IZhO18_chessboard)	C++17	70 / 100	208 ms	3496 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 256;

long long n, k;
int x[MAXN], y[MAXN];
long long res;

inline void f(long long len) {
	long long cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < k; ++i) {
		if ((x[i] / len % 2) == (y[i] / len % 2)) {
			++cnt1;
		} else {
			++cnt2;
		}
	}
	long long e;
	e = ((n/len*n/len + 1) / 2);
	res = min(res, cnt2 + len * len * e - cnt1);
	e = (n/len*n/len) - e;
	res = min(res, cnt1 + len * len * e - cnt2);
} 

int main() {
	scanf("%lld%lld", &n, &k);
	res = n * n;
	
	for (int i = 0; i < k; ++i) {
		scanf("%d%d", x + i, y + i);
		scanf("%d%d", x + i, y + i);
		--x[i];
		--y[i];
	}

	for (int len = 1; len * len <= n; ++len) {
		if (n % len == 0) {
			f(len);
			if (n / len != n) f(n / len);
		}
	}
	
	printf("%lld\n", res);
	
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%lld%lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
chessboard.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d%d", x + i, y + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
chessboard.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d%d", x + i, y + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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