Submission #1133918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133918		Halym2007	Chessboard (IZhO18_chessboard)	C++17	39 / 100	59 ms	1864 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 <int> v;
ll ans = 1e14;
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;
	}
//	sort (p + 1, p + k + 1);
//	for (int i = 1; i <= k; ++i) {
//		cout << p[i].ff << " " << p[i].ss << "\n";
//	}
//	return 0;
	for (int 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 + 2 * ak;
		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++;	
//				if (bol == 4)
//					cout << "---> owur --> " << p[i].ff << " " << p[i].ss << "\n";			
			}
		}
//		if (bol == 4) {
//			cout << opyshy_gara << " " << ak; 
//			return 0;
//		}
		// yzyny dowam etmeli
		ll jogap1 = opyshy_gara - k + 2 * ak;
		ans = min ({ans, jogap, jogap1});
//		if (ans == 14) {
//			cout << jogap << " " << jogap1;
//			return 0;
//		}
	}
	cout << ans << "\n";
}

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