Submission #1134440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134440		Halym2007	Chessboard (IZhO18_chessboard)	C++17	100 / 100	115 ms	4228 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <ll, ll>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
pii p[N], q[N];
vector <ll> v;
ll n, k1, ans = 1e18, a[N];
int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k1;
	for (ll i = 1; i < n; ++i) {
		if (n % i == 0) {
			v.pb (i);
		}
	}
	ll k = 0;
	for (int i = 1; i <= k1; ++i) {
		cin >> p[i].ff >> p[i].ss >> q[i].ff >> q[i].ss;
		k += (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1);
	}
	for (ll bol : v) {
		// 1-nji ak bolsa
		for (ll i = 1; i <= n; ++i) {
			a[i] = ((i + bol - 1) / bol) % 2;
			a[i] += a[i - 1]; 
		}
		// ilki 1-nji block gara renkde bolsa shol variant-da seretyas
		ll jogap = 0, ak = 0;
		ll opyshy_gara = (a[n] * a[n]) + (n - a[n]) * (n - a[n]);
		for (int i = 1; i <= k1; ++i) {
			ll val1 = (a[q[i].ss] - a[p[i].ss - 1]) * (a[q[i].ff] - a[p[i].ff - 1]);
			ll val2 = (q[i].ss - p[i].ss + 1) - (a[q[i].ss] - a[p[i].ss - 1]);
			ll val3 = (q[i].ff - p[i].ff + 1) - (a[q[i].ff] - a[p[i].ff - 1]);
			val2 *= val3;
			ll val4 = (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1);
			ak += val4 - (val2 + val1);
		}
		jogap = (opyshy_gara - k) + (ak * 2LL);
		// indi gara etyas
		ak = 0;	
		ll kk = (n * n) - opyshy_gara;
		opyshy_gara = kk;
		for (int i = 1; i <= k1; ++i) {
			ll val1 = (a[q[i].ss] - a[p[i].ss - 1]) * (a[q[i].ff] - a[p[i].ff - 1]);
			ll val2 = (q[i].ss - p[i].ss + 1) - (a[q[i].ss] - a[p[i].ss - 1]);
			ll val3 = (q[i].ff - p[i].ff + 1) - (a[q[i].ff] - a[p[i].ff - 1]);
			val2 *= val3;
			ll val4 = (q[i].ff - p[i].ff + 1) * (q[i].ss - p[i].ss + 1);
			ak += val2 + val1;
		}
		ll jogap1 = (opyshy_gara - k) + (ak * 2LL);
		ans = min ({ans, jogap, jogap1});
	}
	cout << ans << "\n";
}

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