Submission #760482

#	Time	Username	Problem	Language	Result	Execution time	Memory
760482		NK_	Chessboard (IZhO18_chessboard)	C++17	100 / 100	325 ms	4184 KiB

chessboard

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;

using ll = long long;
const ll INFL = ll(1e18) + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	// ONLY SQRT(N) WIDTHS

	int N, K; cin >> N >> K;

	V<AR<int, 4>> A(K); 
	for(auto& x : A) cin >> x[0] >> x[1] >> x[2] >> x[3];

	V<int> div;
	for(int i = 1; i*i <= N; i++) {
		if (N % i == 0) {
			div.pb(i);
			if (i*i != N) div.pb(N / i);
		}
	}

	sort(begin(div), end(div)); div.pop_back();

	ll ans = INFL;
	for(auto& w : div) {
		int n = N / w;

		AR<ll, 2> res = {((n * 1LL * n) / 2) * w * 1LL * w, ((n * 1LL * n + 1) / 2) * w * 1LL * w};
		// res[0] -> top-left is white, res[1] -> top-left is black

		for(auto x : A) {
			auto [r, c, R, C] = x; --r, --c, --R, --C;

			// BLACK AND WHITE PER ROW (FOR FIRST ROW)
			int BPR = 0, WPR = 0;
			// CHECK (r, c) and (r, C)

			int wr = r / w, wc = c / w, wC = C / w, wR = R / w;

			int Crc = (wr + wc) % 2, CrC = (wr + wC) % 2;

			if (wc == wC) (Crc == 0 ? WPR += C - c + 1 : BPR += C - c + 1);
			else {
				int LB = (wc + 1) * w - 1; 
				(Crc == 0 ? WPR += LB - c + 1 : BPR += LB - c + 1);

				int RB = wC * w;
				(CrC == 0 ? WPR += C - RB + 1 : BPR += C - RB + 1);

				int LEN = (RB - 1) - (LB + 1) + 1;
				assert(LEN % w == 0); int BLK = LEN / w; 

				if (Crc == 0) BPR += ((BLK + 1) / 2) * w, WPR += (BLK / 2) * w;
				else WPR += ((BLK + 1) / 2) * w, BPR += (BLK / 2) * w;
			}

			// OBVERSED AND INVERSED ROWS
			int OPR = 0, IPR = 0;

			if (wr == wR) OPR += R - r + 1;
			else {
				int LB = (wr + 1) * w - 1; 
				OPR += LB - r + 1;

				int LEN = R - (LB + 1) + 1;
				int BLK = LEN / w; int LEFT = LEN % w;

				IPR += ((BLK + 1) / 2) * w; OPR += (BLK / 2) * w;

				if (BLK % 2) OPR += LEFT;
				else IPR += LEFT;
			}

			ll BLACKS = BPR * 1LL * OPR + WPR * 1LL * IPR;
			ll WHITES = WPR * 1LL * OPR + BPR * 1LL * IPR;

			// cout << BLACKS << " - " << WHITES << nl;


			res[0] += WHITES - BLACKS; res[1] += BLACKS - WHITES;
		}

		// cout << res[0] << " " << res[1] << nl;
		ans = min(ans, min(res[0], res[1]));
	}

	cout << ans << nl;






    return 0;
}

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