Submission #1143637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143637		Agageldi	Chessboard (IZhO18_chessboard)	C++17	39 / 100	46 ms	3400 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 400005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define rep(c, a, b) for(c = a; c <= b; c++)

ll n, t, y, answer = INT_MAX, k, p, o[N], u[N], z[N], g[N];
vector <ll> v;

void solve1(ll x,ll dv) {
	ll white = (x + 1) / 2, black = (x / 2);
	ll c = 0,c_c = 0, r = 0, ak = 0, gara = 0;
	for(int i = 1; i <= k; i++) {
		c_c = (o[i] + dv - 1) / dv;
		r = (c_c % 2 == 1 ? 0 : 1);
		c_c = (z[i] + dv - 1) / dv;
		c = (c_c % 2 == 1 ? 0 : 1);
		if(r == c) ak++;
	}
	answer = min(answer, ak + (black * dv * dv - (k - ak)));
}
void solve2(ll x,ll dv) {
	ll white = x / 2, black = (x + 1) / 2;
	ll c = 0,c_c = 0, r = 0, ak = 0, gara = 0;
	for(int i = 1; i <= k; i++) {
		c_c = (o[i] + dv - 1) / dv;
		r = (c_c % 2 == 1 ? 0 : 1);
		c_c = (z[i] + dv - 1) / dv;
		c = (c_c % 2 == 1 ? 0 : 1);
		if(r == c) gara++;
	}
	answer = min(answer, (k - gara) + (black * dv * dv - gara));
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= k; i++) {
		cin >> o[i] >> z[i] >> u[i] >> g[i];
	}
	for(int i = 1; i < n; i++) {
		if(n % i == 0) v.pb(i);
	}
	for(auto i : v) {
		ll s_q = (n * n) / (i * i);
		solve1(s_q,i);
		solve2(s_q,i);
	}
	cout << answer << '\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