제출 #378765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378765		Kevin_Zhang_TW	Chessboard (IZhO18_chessboard)	C++17	100 / 100	447 ms	3436 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

#define int ll

const int MAX_N = 300010;

int n, k;
vector<tuple<int,int,int,int>> subr;

ll calgood(int w, int x1, int y1, int x2, int y2) {

//	{
//	ll res = 0;
//	for (int i = x1;i <= x2;++i)
//		for (int j = y1;j <= y2;++j) {
//			int need = (1^(i/w) ^ (j/w))&1;
//			res += need;
//		}
//	return res;
//	}

	ll res = 0;

	ll a = 0, b = 0, c = 0, d = 0;

	auto cal = [&](ll l, ll r, ll ot) -> pair<ll,ll> {
		ll a = 0, b = 0;
		ll lid = l / w +1, rid = r / w - 1;

		if (lid <= rid) {
			ll even = (rid/2) - ((lid-1)/2), odd = rid-lid+1-even;
			a += even * w;
			b += odd * w;
		}

		{
			ll L = l, R = min(r, lid * w - 1);

			if (((1^(l/w))&1))
				a += R-L+1;
			else
				b += R-L+1;
		}
		if (lid-1 != rid+1) {
			ll L = max(l, (rid+1) * w), R = r;

			if (((1^(r/w))&1))
				a += R-L+1;
			else
				b += R-L+1;
		}

//		for (int i = l;i <= r;++i)
//			if (((1^(i/w))&1))
//				++a;
//			else
//				++b;

		if (ot) swap(a, b);
		return {a, b};
	};

	tie(a, b) = cal(x1, x2, y1/w);

	tie(c, d) = cal(y1, y2, y1/w);

	return a * c + b * d;
}
ll calcost(int wid) {
	ll res = calgood(wid, 0, 0, n-1, n-1);
	for (auto [x1, y1, x2, y2] : subr) {
		ll area = 1ll * (x2-x1+1) * (y2-y1+1);
		ll good = calgood(wid, x1, y1, x2, y2);
		ll bad = area - good;
		res -= good;
		res += bad;
	}

	return min(res, 1ll * n * n - res);
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	DE(n, k);

	//if (n > 1000) return -1;
	subr.resize(k);
	for (auto &[x1, y1, x2, y2] : subr)
		cin >> x1 >> y1 >> x2 >> y2, --x1, --x2, --y1, --y2;

	ll res = 1ll * n * n;

	for (int i = 1;i < n;++i)
		if (n % i == 0)
			chmin(res, calcost(i));

	cout << res << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp: In function 'll calgood(ll, ll, ll, ll, ll)':
chessboard.cpp:37:5: warning: unused variable 'res' [-Wunused-variable]
   37 |  ll res = 0;
      |     ^~~
chessboard.cpp: In function 'int32_t main()':
chessboard.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
chessboard.cpp:99:2: note: in expansion of macro 'DE'
   99 |  DE(n, k);
      |  ^~

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