Submission #40565

#	Time	Username	Problem	Language	Result	Execution time	Memory
40565		Just_Solve_The_Problem	Chessboard (IZhO18_chessboard)	C++11	100 / 100	1409 ms	3820 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define whatis(x) cout << #x << " is -> " << x << endl;

const ll linf = (ll)1e18 + 7;
const ll N = (ll)1e5 + 7;

ll x1[N], YY[N], x2[N], y2[N];

ll n;
ll k;
ll ans = linf;

inline ll gety(ll y,ll len){
	if(y <= 0) return 0;
	ll res = (y / len) / 2 * len;
	if((y / len) & 1) res += y % len + 1;
	return res;
}

inline ll getx(ll x,ll len){
	if(x <= 0) return 0;
	ll res = (x / len) / 2 * len;
	if((x / len) & 1) res += x % len + 1;
	return res;
}

void calc(ll len) {
  ll odd = 0, even = 0;
	for(ll i = 1,xx,yy; i <= k; i++){
		ll o1 = gety(y2[i], len) - gety(YY[i] - 1, len);
		ll e1 = (y2[i] - YY[i] + 1) - o1;
		ll o2 = getx(x2[i], len) -  getx(x1[i] - 1, len);
		ll e2 = (x2[i] - x1[i] + 1) - o2;
		xx = x1[i] / len;
		yy = YY[i] / len;
		if(xx & 1) swap(o1,e1);
		if(yy & 1) swap(o2,e2);
		ll od = 0, ev = 0;
		if((xx + yy) & 1){
			od = e1 * e2 + o1 * o2;
		}
		else{
		    od = o1 * e2 + e1 * o2;
		}
		ev = 1ll * (x2[i] - x1[i] + 1) * (y2[i] - YY[i] + 1) - od;

		odd += od;
		even += ev;
	}
	ll cnt = 1ll * (n / len) * (n / len);
	ll res = min(cnt / 2 * len * len + even - odd, (cnt + 1) / 2 * len * len + odd - even);
	if(res < ans){
		ans = res;
	}
}

main () {
  scanf("%lld %d", &n, &k);
  for (ll i = 1; i <= k; i++) {
    ll a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
    a--; b--; c--; d--;
    x1[i] = a; YY[i] = b; x2[i] = c; y2[i] = d;
  }
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      calc(i);
      if (i != 1 && n / i != i) calc(n / i);
    }
  }
  printf("%lld", ans);
}

Compilation message (stderr)

chessboard.cpp:61:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
chessboard.cpp: In function 'int main()':
chessboard.cpp:62:26: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   scanf("%lld %d", &n, &k);
                          ^
chessboard.cpp:64:55: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     ll a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
                                                       ^
chessboard.cpp:64:55: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
chessboard.cpp:64:55: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
chessboard.cpp:64:55: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'long long int*' [-Wformat=]
chessboard.cpp:62:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %d", &n, &k);
                           ^
chessboard.cpp:64:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ll a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
                                                        ^

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