Submission #492737

#	Time	Username	Problem	Language	Result	Execution time	Memory
492737		hollwo_pelw	Chessboard (IZhO18_chessboard)	C++17	100 / 100	319 ms	5828 KiB

chessboard

/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
	if (fopen(filein.c_str(), "r")){
		freopen(filein.c_str(), "r", stdin);
		freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
		freopen(fileerr.c_str(), "w", stderr);
#endif
	}
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}

void Hollwo_Pelw();

signed main(){
#ifdef hollwo_pelw_local
	FAST_IO("input.inp", "output.out", "error.err");
	auto start = chrono::steady_clock::now();
#else
	FAST_IO("hollwo_pelw.inp", "hollwo_pelw.out");
#endif
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
	return 0;
}

#define int long long

const int N = 1e5 + 5;

struct rect_t {
	int x1, y1, x2, y2;
	rect_t(int _x1 = 0, int _y1 = 0, int _x2 = 0, int _y2 = 0)
		: x1(_x1), y1(_y1), x2(_x2), y2(_y2) {}
} a[N];

int n, m;

inline int get(int i, int k) {
	return min(i % (2 * k), k) + i / (2 * k) * k;
}

inline int solve(int k) {
	int cnt = n * n / (k * k);
	int res = (cnt / 2) * (k * k);

	// cout << "solve " << k << '\n';

	for (int i = 1; i <= m; i++) {
		auto [x1, y1, x2, y2] = a[i];

		// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';

		int H = x2 - x1 + 1;
		int W = y2 - y1 + 1;
		int tot = H * W;

		// cout << H << ' ' << W << '\n';

		int h = get(x2, k) - get(x1 - 1, k);
		int w = get(y2, k) - get(y1 - 1, k);

		// cout << h << ' ' << w << '\n';

		int black = h * w + (H - h) * (W - w);
		res = res - tot + 2 * black;
	}
	return min(n * n - res, res);
}


void Hollwo_Pelw() {
	cin >> n >> m;
	for (int i = 1, x1, y1, x2, y2; i <= m; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		a[i] = rect_t(x1, y1, x2, y2);
	}

	int res = 1e18;
	for (int i = 1; i < n; i++) 
		if (n % i == 0) res = min(res, solve(i));

	cout << res;
}

Compilation message (stderr)

chessboard.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
chessboard.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen(filein.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
chessboard.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(fileout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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