Submission #1149459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149459		aktilek	Chessboard (IZhO18_chessboard)	C++20	39 / 100	39 ms	3564 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 2e5 + 7;
const int R = 1e9 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int B = 320;

bool primen(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x % i == 0) {
			return false;
		}
	}
	
	return true;
}

void solve() {
	int n, k;
	cin >> n >> k;
	
	if (primen(n)) {
				ll a = 0, b = 0;
		for (int i = 1; i <= k; i++) {
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			
			if ((x1 + y1) % 2 == 0) {
				a++;
			} else {
				b++;
			}
		}
		
		ll needa = 0, needb = 0;
		for (int i = 1; i <= n; i++) {
			if (i % 2 == 0) {
				needb += i;
			} else {
				needa += i;
			}
		}
		
		needa *= 2;
		needb *= 2;
		
		needa -= n;
		
		// cout << needa << ' ' << needb << '\n';
		
		cout << min(needa - a + b, needb - b + a) << '\n';
		return;
	}
	
		int x1[N], y1[N], x2[N], y2[N];
		
		for (int i = 1; i <= k; i++) {
			cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
		}
		
		ll ans = R;
		
		for (int i = 1; i <= sqrt(n); i++) {
			if (n % i == 0) {
				ll needa = 0, needb = 0;
				ll a = 0, b = 0;
				for (int j = 1; j <= k; j++) {
					int ox = x1[j] / i;
					int oy = y1[j] / i;
					if (x1[j] % i != 0) ox++;
					if (y1[j] % i != 0) oy++;
					
					if ((ox + oy) % 2 == 0) a++;
					else b++;
					
					// cout << ox << ' ' << oy << '\n';
				} 
				
				for (int j = 1; j <= n / i; j++) {
					if (j % 2 == 0) {
						needa += j;
						if (j != n / i) needa += j;
					} else {
						needb += j;
						if (j != n / i) needb += j;
					}
				}
				
				// cout << needa << ' ' << needb << '\n';
				
				if ((n / i) % 2 == 1)
					swap(a, b);
				
				ans = min(ans, min(needa * i * i - a + b, needb * i * i - b + a));
				// cout << needa * i * i - a + b << '\n';
				// cout << needb * i * i - b + a << '\n';
				if (i == 1) continue;
				needa = 0, needb = 0;
				a = 0, b = 0;
				for (int j = 1; j <= k; j++) {
					int ox = x1[j] / (n / i);
					int oy = y1[j] / (n / i);
					if (x1[j] % (n / i) != 0) ox++;
					if (y1[j] % (n / i) != 0) oy++;
					
					// cout << ox << ' ' << oy << '\n';
					
					if ((ox + oy) % 2 == 0) a++;
					else b++;
				}
				
				for (int j = 1; j <= i; j++) {
					if (j % 2 == 0) {
						needa += j;
						if (j != i) needa += j;
					} else {
						needb += j;
						if (j != i) needb += j;
					}
				}
				
				if (i % 2 == 1) swap(a, b);
				
			
				// cout << needa << ' ' << needb << '\n';
				// cout << a << ' ' << b << '\n';
				
				// cout << needa * (n / i) * (n / i) - a + b << '\n';
				ans = min(ans, min(needa * (n / i) * (n / i) - a + b, needb * (n / i) * (n / i) - b + a));
			}
		}
		
		cout << ans << '\n';
		return;
	
}

int main() {
  	// freopen("gates.in", "r", stdin);
  	// freopen("gates.out", "w", stdout);
  	Fast
  
  	int tc = 1;
  	// cin >> tc;
  
  	while (tc--) {
    	solve();
  	}
}

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