Submission #385601

#	Time	Username	Problem	Language	Result	Execution time	Memory
385601		patrikpavic2	Chessboard (IZhO18_chessboard)	C++17	100 / 100	433 ms	6548 KiB

chessboard

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll N = 2e5 + 500;

ll n, k, xx1[N], xx2[N], yy1[N], yy2[N], P[N];
ll pov = 0;

ll stranica(ll st, ll x1, ll x2){
	return P[x2] - (x1 ? P[x1 - 1] : 0);
}

bool boja(ll st, ll x, ll y){
	return ((x / st) + (y / st)) & 1;
}

ll calc(ll st, ll x1, ll y1, ll x2, ll y2){
	ll dx = stranica(st, x1, x2);
	ll dy = stranica(st, y1, y2);
	if(x1 / st == x2 / st)
		return (x2 - x1 + 1) * (boja(st, x1, 0) ? (y2 - y1 + 1 - dy) : dy);
	if(y1 / st == y2 / st)
		return (y2 - y1 + 1) * (boja(st, y1, 0) ? (x2 - x1 + 1 - dx) : dx);
	ll ux1 = x1 + (st - x1 % st) % st;
	ll uy1 = y1 + (st - y1 % st) % st;
	ll ux2 = x2 - (x2 % st  + 1) % st;
	ll uy2 = y2 - (y2 % st + 1) % st;
	ll rub = 0;
	rub += (ll)(boja(st, 0, y1) ? (x2 - x1 + 1) - dx : dx) * (uy1 - y1);
	rub += (ll)(boja(st, 0, y2) ? (x2 - x1 + 1) - dx : dx) * (y2 - uy2);
	rub += (ll)(boja(st, x1, 0) ? (y2 - y1 + 1) - dy : dy) * (ux1 - x1);
	rub += (ll)(boja(st, x2, 0) ? (y2 - y1 + 1) - dy : dy) * (x2 - ux2);
	if(boja(st, x1, y1)) rub -= (ll)(ux1 - x1) * (uy1 - y1);	
	if(boja(st, x1, y2)) rub -= (ll)(ux1 - x1) * (y2 - uy2);	
	if(boja(st, x2, y1)) rub -= (ll)(x2 - ux2) * (uy1 - y1);	
	if(boja(st, x2, y2)) rub -= (ll)(x2 - ux2) * (y2 - uy2);	
//	prllf("rub = %lld\n", rub);
	ll sred = 0;
	ll Dx = (ux2 - ux1 + 1) / st;
	ll Dy = (uy2 - uy1 + 1) / st;
	//prllf("Dx = %d Dy = %d\n", Dx, Dy);
	sred += (ll)st * st * ((ll)Dx * Dy / 2LL + (boja(st, ux1, uy1) && ((Dx & 1) && (Dy & 1))));
	return rub + sred;	
}

int main(){
	scanf("%lld%lld", &n, &k);	
	for(ll i = 0;i < k;i++){
		scanf("%lld%lld%lld%lld", xx1 + i, yy1 + i, xx2 + i, yy2 + i);
		xx1[i]--, xx2[i]--, yy1[i]--, yy2[i]--;
		pov += (ll)(xx2[i] - xx1[i] + 1) * (yy2[i] - yy1[i] + 1);
	}
	ll sol = (ll)n * n;
	for(ll i = 1;i < n;i++){
		if(n % i) continue;
		for(ll j = 0;j < n;j++)
			P[j] = (j ? P[j - 1] : 0) + ((j / i) & 1);
		ll cur = 0;
		for(ll j = 0;j < k;j++)
			cur += calc(i, xx1[j], yy1[j], xx2[j], yy2[j]);
		//printf("		cur = %lld\n", cur);
		ll crnih = (ll)i * i * (((ll)(n / i) * (n / i)) / 2LL);
		//printf("crnih = %lld\n", crnih);
		cur = crnih - cur + pov - cur;
		//printf("cur = %lld\n", cur);
		sol = min(sol, cur);
		sol = min(sol, (ll)n * n - cur);
	}
	printf("%lld\n", sol);
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  scanf("%lld%lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
chessboard.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   scanf("%lld%lld%lld%lld", xx1 + i, yy1 + i, xx2 + i, yy2 + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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