Submission #555280

#	Time	Username	Problem	Language	Result	Execution time	Memory
555280		ngpin04	Chessboard (IZhO18_chessboard)	C++14	70 / 100	2081 ms	3416 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[2 * N];
int lim[2 * 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);
	int base = getv(x, y, l, val);
	if (dx > dy)
		swap(dx, dy);

	if (dx < l) {
		if (dy < l) 
			res = (long long) dx * dy;
		else {
			if (par[dy] & 1)
				res = (long long) dx * l; 
		}
	} else {
		if (par[dx] & par[dy] & 1)
			res = (long long) l * l;
	}
	if (base < 0)
		res = -res;
	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 i = 0; i < 2 * n; i++) {
			par[i] = (i / l);
			lim[i] = par[i] * l;
		}
		
		for (int val = 0; val < 2; val++) {
			int d = (n / l);
			long long res = ((1LL * d * d + val) >> 1) * l * 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 = lim[x + l - 1];
				int j = lim[y + l - 1];
				int s = lim[u + 1] - 1;
				int t = lim[v + 1] - 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));
					if (i <= s) 
						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));
					if (j <= t) 
						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