Submission #93090

#	Time	Username	Problem	Language	Result	Execution time	Memory
93090		Makhsud	Chessboard (IZhO18_chessboard)	C++17	47 / 100	141 ms	504 KiB

chessboard

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

ll n, k, x, y, xx, yy;
ll 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) );
}
ll d[50000][5][5];
vector<ll>divs;
void subt3()
{
	for ( int i = 1; i < n; i ++ ){
		if ( n % i == 0 ){
			divs.push_back((ll)i);
		}
	}
	for ( int i = 1; i <= k; i ++ ) {
		cin >> x >> y >> xx >> yy;
		for ( auto e: divs ) {
			ll c, r;
			r = ( x / e ) + ((x % e) && 1 );
			c = ( y / e ) + ((y % e) && 1 );
			d[e][r%2][c%2] ++;
		}
	}
	ll cnt1 = 0, cnt2 = 0, mn = INT_MAX;
	for ( auto e: divs ){
		cnt1 = cnt2 = 0;
		for ( int i = 1; i <= n/e; i ++ ) {
			if ( i % 2 == 1 ) {
				cnt1 += ( (e*e) * ( ( n / e ) / 2 ) );
				cnt2 += ( (e*e) * ( ( ( n / e ) +1 ) / 2 ) );
			} else {
				cnt1 += ( (e*e) * ( ( ( n / e ) +1 ) / 2 ) );
				cnt2 += ( (e*e) * ( ( n / e ) / 2 ) );
			}
		}
		cnt1 += (d[e][1][1] + d[e][0][0]);
		cnt1 -= (d[e][1][0] + d[e][0][1]);

		cnt2 += (d[e][1][0] + d[e][0][1]);
		cnt2 -= (d[e][1][1] + d[e][0][0]);
		mn = min( mn, min( cnt1, cnt2 ) );
	}
	cout << mn;
}

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 ) {
		subt3();
		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