Submission #1133925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133925		Halym2007	Chessboard (IZhO18_chessboard)	C++17	70 / 100	272 ms	2016 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 <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
int n, k;
pii p[N], q[N];
vector <ll> v;
ll ans = 1e18;
int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i < n; ++i) {
		if (n % i == 0) {
			v.pb (i);
		}
	}
	for (int i = 1; i <= k; ++i) {
		cin >> p[i].ff >> p[i].ss >> q[i].ff >> q[i].ss;
		assert (p[i].ff == q[i].ff);
		assert (p[i].ss == q[i].ss);
	}
	for (ll bol : v) {
		// 1-nji ak bolsa
		ll jogap = 0, ak = 0;
		ll opyshy_gara = (((n / bol) * (n / bol)) / 2) * bol * bol;
		for (int i = 1; i <= k; ++i) {
			int a1 = (p[i].ff + bol - 1) / bol, b1 = (p[i].ss + bol - 1) / bol;
			if (a1 % 2 == b1 % 2) {
				ak++;
			}
		}
		jogap = (opyshy_gara - k) + (ak * 2LL);
		// indi gara etyas
		ak = 0;		
		opyshy_gara = ((((n / bol) * (n / bol)) + 1) / 2) * bol * bol;
		for (int i = 1; i <= k; ++i) {
			int a1 = (p[i].ff + bol - 1) / bol, b1 = (p[i].ss + bol - 1) / bol;
			if ((a1 % 2 == 1 and b1 % 2 == 0) or (a1 % 2 == 0 and b1 % 2 == 1)) {
				ak++;	
			}
		}
		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: 0 / 30