제출 #555274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555274		ngpin04	Chessboard (IZhO18_chessboard)	C++14	70 / 100	2001 ms	4620 KiB

chessboard

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

pair <int, int> a[N], b[N];

int par[N];
int n,k;

int getc(int i, int j, int l, int val) {
	return ((par[i] ^ par[j]) & 1) ^ val;
}

int getv(int i, int j, int l, int val) {
	return (getc(i, j, l, val) > 0) ? -1 : 1;
}

long long calc(int x, int y, int u, int v, int l, int val) {
	if (x > u || y > v)
		return 0;	

	long long res = 0;
	int dx = (u - x + 1);
	int dy = (v - y + 1);
	if (dx > dy)
		swap(dx, dy);

	if (dx < l) {
		if (dy < l) 
			res = (long long) dx * dy * getv(x, y, l, val);
		else {
			if ((dy / l) & 1)
				res = (long long) dx * l * getv(x, y, l, val); 
		}
	} else {
		if (par[dx] & par[dy] & 1)
			res = (long long) l * l * getv(x, y, l, val);
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> k;

	for (int i = 1; i <= k; i++) {
		cin >> a[i].fi >> a[i].se >> b[i].fi >> b[i].se;
		a[i].fi--; a[i].se--;
		b[i].fi--; b[i].se--;
	}

	long long ans = ooo;
	for (int l = 1; l < n; l++) if (n % l == 0) 
	for (int val = 0; val < 2; val++) {
		int d = (n / l);
		long long res = ((1LL * d * d + val) >> 1) * l * l;
		for (int i = 0; i < n; i++)
			par[i] = (i / l);

		for (int id = 1; id <= k; id++) {
			int x = a[id].fi;
			int y = a[id].se;
			int u = b[id].fi;
			int v = b[id].se;

			int i = (x + l - 1) / l * l;
			int j = (y + l - 1) / l * l;
			int s = (u + 1) / l * l - 1;
			int t = (v + 1) / l * l - 1;
			vector <pair <int, int>> r, c;
			if (par[x] == par[u])
				r.push_back(mp(x, u));
			else {
				r.push_back(mp(x, i - 1));
				r.push_back(mp(i, s));
				r.push_back(mp(s + 1, u));
			}
			if (par[y] == par[v])
				c.push_back(mp(y, v));
			else {
				c.push_back(mp(y, j - 1));
				c.push_back(mp(j, t));
				c.push_back(mp(t + 1, v));
			}

			for (pair <int, int> a : r)
			for (pair <int, int> b : c)
				res += calc(a.fi, b.fi, a.se, b.se, l, val);
		}
		// cerr << "split: " << l << " " << val << " " << res << "\n";
		mini(ans, res);
	}

	cout << ans;
	return 0;
}

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