| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 40563 | Just_Solve_The_Problem | Chessboard (IZhO18_chessboard) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 int N = (int)1e5 + 7;
int x1[N], y1[N], x2[N], y2[N];
ll n;
int 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(int i = 1,xx,yy; i <= k; i++){
ll o1 = gety(y2[i], len) - gety(y1[i] - 1, len);
ll e1 = (y2[i] - y1[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 = y1[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] - y1[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 (int i = 1; i <= k; i++) {
int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
a--; b--; c--; d--;
x1[i] = a; y1[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("%I64d", ans);
}