Submission #634762

#	Time	Username	Problem	Language	Result	Execution time	Memory
634762		lovrot	Chessboard (IZhO18_chessboard)	C++11	100 / 100	1385 ms	8920 KiB

chessboard

#include <bits/stdc++.h>

#define pii pair<ll, ll>
#define X first
#define Y second
#define ll long long

using namespace std; 

const int N = 2 * 1e5 + 10;
const ll INF = 1e12;

ll n, m, d;
pii rect[N][4];  
bool b;

bool getCol(ll x, ll y){ 
	if(((x & 1) == (y & 1))) return b;
	return !b;
}

ll rectangle(ll x, ll y){ 
	ll ret = ((x * y) / 2) * d * d;
	if((x & 1) && (y & 1))
		ret += b ? d * d : 0;
	return ret;
}

ll area(ll x, ll y){ 
	if((x & 1) && (y & 1)){ 
		if(b) return -(d * d);
		else return d * d;
	}
	return 0;
}

ll calcPart(ll w, ll h, bool col){ 
	if(col){ 
		return (h & 1) ? -(w * d) : 0; 
	} 
	return (h & 1) ? w * d : 0;
}

ll pref(pii p){
	ll x = p.X;
	ll y = p.Y; 
	ll lenx = x / d, leny = y / d;
	ll ret = area(lenx, leny);
	x = x % d;
	y = y % d;

	if(getCol(lenx, leny)) ret -= x * y;
	else ret += x * y;
	ret += calcPart(x, leny, getCol(lenx, 0));
	ret += calcPart(y, lenx, getCol(0, leny));
	return ret;
}

int main(){ 
	scanf("%lld%d", &n, &m);

	for(int i = 0; i < m; i++){ 
		ll x, y, x2, y2;
		scanf("%lld%lld%lld%lld", &x, &y, &x2, &y2);
		rect[i][0] = {x2, y2};
		rect[i][2] = {x - 1, y - 1};
		rect[i][1] = {x - 1 , y2};		
		rect[i][3] = {x2, y - 1};
	}

	ll ans = INF;
	for(int i = 1; i < n; i++){ 
		if(n % i) continue;
		d = i;
		for(int nb = 0; nb < 2; nb++){
			b = nb;
			ll res = rectangle(n / d, n / d);
			for(int j = 0; j < m; j++){
				res += pref(rect[j][0]) - pref(rect[j][1]) + pref(rect[j][2]) - pref(rect[j][3]); 	
				// if(i == 5) cout << pref(rect[j][0]) - pref(rect[j][1]) + pref(rect[j][2]) - pref(rect[j][3]) << " +\n";
			}
			// printf("%d %d %d %d\n", i, nb, rectangle(n / d, n / d), res);
			ans = min(ans, res);
		}	
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:60:14: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   60 |  scanf("%lld%d", &n, &m);
      |             ~^       ~~
      |              |       |
      |              int*    long long int*
      |             %lld
chessboard.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%lld%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
chessboard.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%lld%lld%lld%lld", &x, &y, &x2, &y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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