Submission #92978

#	Time	Username	Problem	Language	Result	Execution time	Memory
92978		Makhsud	Chessboard (IZhO18_chessboard)	C++17	47 / 100	128 ms	5268 KiB

chessboard

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

ll n, k, x, y, xx, yy;
ll d, mn = INT_MAX;

ll ch ( ll del ) {
	ll ans = 0;
	if ( del == 1 ) {
		return (n*n)/2;
	}
	for ( int i = 1; i <= (n/del); i ++ ) {
		if ( i % 2 == 1 ) {
			ans += (del*del) * ( (n/del) / 2 );

		}
		else {
			ans += (del*del) * ( ( ( n/del )+1) / 2 );

		}
	}
	return ans;
}
ll a[5][5];
void subt2()
{
	for ( int i = 1; i <= k; i ++ ) {
		cin >> x >> y >> xx >> yy;
		a[x%2][y%2]++;
	}
	ll a1 = 0, a2 = 0;
	a1 = (n*n) / 2;
	a2 = a1 + 1;

	a2 = a2 - (a[1][1] + a[0][0]);
	a2 = a2 + (a[1][0] + a[0][1]);

	a1 = a1 - (a[1][0] + a[0][1]);
	a1 = a1 + (a[1][1] + a[0][0]);

	cout << min ( (a1), (a2) );
}
bool used[10005][10005];
ll NumOfPainted( ll s, ll e, ll de ) {
	ll num = 0;
	for ( int i = s; i <= s+de-1; i ++ ){
		for ( int j = e; j <= e+de-1; j ++ ) {
			if ( used[i][j] ) num ++;
		}
	}
	return num;
}
ll subt3( ll del )
{
	ll cnt1 = 0, cnt2 = 0, c=0, d=0;
	for ( int i = 1; i <= n; i += del ) {
		c ++;
		for ( int j = 1; j <= n; j += del ) {
			d ++;
			if ( (c % 2 == 1 && d % 2 == 0) || (c % 2 == 0 && d % 2 == 1) ) {
				cnt1 += ( (del*del) - NumOfPainted(i,j,del) );
				cnt2 += NumOfPainted(i,j,del);
			}
			if ( (c % 2 == 1 && d % 2 == 1) || (c % 2 == 0 && d % 2 == 0) ) {
				cnt1 += NumOfPainted(i,j,del);
				cnt2 += ( (del*del) - NumOfPainted(i,j,del) );
			}
		}
		d = 0;
	}
	return min(cnt1,cnt2);
}

int main()
{
	cin >> n >> k;
	ll cnt = 0;
	for ( int i = 1; i <= n; i ++ )
		if ( n % i == 0 ) cnt ++;

	if ( cnt == 2 ){
		subt2();
		return 0;
	}

	if ( k != 0 ) {
		ll MN = INT_MAX;
		for ( int i = 1; i <= k; i ++ ) {
			cin >> x >> y >> xx >> yy;
			used[x][y] = true;
		}
		for ( int i = 1; i < n; i ++ ) {
			if ( n % i == 0 ) {
				ll an = subt3(i);
				//cout << an << '\n';
				MN = min (MN, an);
			}
		}
		cout << MN;
		return 0;
	}

	for ( int i = 1; i < n; i ++ ) {
		if ( n % i == 0 ) {
			ll an = ch(i);
			mn = min ( mn, an );
		}
	}
	cout << mn;
}

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