Submission #50841

#	Time	Username	Problem	Language	Result	Execution time	Memory
50841		Nicksechko	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1221 ms	908 KiB

chessboard

#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

pair<ll, ll> operator+(pair<ll, ll> a, pair<ll, ll> b) {
	return make_pair(a.first + b.first, a.second + b.second);
}

pair<ll, ll> operator-(pair<ll, ll> a, pair<ll, ll> b) {
	return make_pair(a.first - b.first, a.second - b.second);
}


pair<ll, ll> get(ll x, ll k) {
	ll kx = x / k;
	if (kx % 2 == 0)
		return make_pair((kx + 1) / 2 * k + x % k, (kx) / 2 * k);
	else
		return make_pair((kx + 1) / 2 * k, (kx) / 2 * k + x % k);
}

const ll MAXN = 120000;

int n, k;
vector<ll> dv;

pair<ll, ll> go[MAXN];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i < n; ++i) {
		if (n % i == 0)
			dv.push_back(i);
	}
	for (int i = 0; i < k; ++i) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		--x1, --y1;
		for (int it = 0; it < dv.size(); ++it) {
			int j = dv[it];
			pair<ll, ll> xx = get(x2, j) - get(x1, j);
			pair<ll, ll> yy = get(y2, j) - get(y1, j);
			go[it] = go[it] + make_pair(xx.first * yy.first + xx.second * yy.second, xx.second * yy.first + xx.first * yy.second);
		}
	}
	ll ans = ll(n) * n;
	for (int i = 0; i < dv.size(); ++i) {
		ll sd = n / dv[i];
		pair<ll, ll> nd = make_pair((sd * sd + 1) / 2 * dv[i] * dv[i], (sd * sd) / 2 * dv[i] * dv[i]);
		ans = min(ans, nd.first - go[i].first + go[i].second);
		ans = min(ans, nd.second - go[i].second + go[i].first);
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int it = 0; it < dv.size(); ++it) {
                    ~~~^~~~~~~~~~~
chessboard.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < dv.size(); ++i) {
                  ~~^~~~~~~~~~~

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