oj.uz

답안 #683131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683131 2023-01-17T19:25:30 Z phoenix Chessboard (IZhO18_chessboard) C++17
0 / 100
 47 ms 2260 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct point {
    ll x, y;
};

// returns number of black ceils on chess board a x b, f - color of first ceil (0 - white, 1 - black)
ll black_nums(ll a, ll b, bool f) {
    if(a < 0 || b < 0) return 0;
    if(f) return ((a + 1) >> 1) * ((b + 1) >> 1) + (a >> 1) * (b >> 1); 
    return (a >> 1) * ((b + 1) >> 1) + ((a + 1) >> 1) * (b >> 1);
}   
ll func(point p1, point p2, ll d, bool cl) {
    ll cp1y = p1.y / d, cp1x = p1.x / d, cp2x = p2.x / d, cp2y = p2.y / d;
    ll x1 = p1.x, x2 = p2.x, y1 = p1.y, y2 = p2.y;
    ll dx1 = ((d - p1.x % d) % d);
    ll dy1 = ((d - p1.y % d) % d);
    ll dx2 = ((p2.x + 1) % d);
    ll dy2 = ((p2.y + 1) % d);
    if((dx1 || dx2) && cp1x == cp2x) dx1 = p2.x - p1.x + 1, dx2 = 0; 
    x1 += dx1; x2 -= dx2;
    if((dx1 || dx2) && cp1y == cp2y) dy1 = p2.y - p1.y + 1, dy2 = 0; 
    y1 += dy1; y2 -= dy2;
    ll cx1 = x1 / d, cy1 = y1 / d;
    ll cnt = 0;
    cnt += black_nums((x2 - x1 + 1) / d, (y2 - y1 + 1) / d, (cl ^ ((cx1 + cy1) & 1))) * d * d;
    cnt += black_nums((x2 - x1 + 1) / d, 1, (cl ^ ((cx1 + cp1y) & 1))) * dy1 * d;
    cnt += black_nums((x2 - x1 + 1) / d, 1, (cl ^ ((cx1 + cp2y) & 1))) * dy2 * d;
    cnt += black_nums(1, (y2 - y1 + 1) / d, (cl ^ ((cp1x + cy1) & 1))) * dx1 * d;
    cnt += black_nums(1, (y2 - y1 + 1) / d, (cl ^ ((cp2x + cy1) & 1))) * dx2 * d;
    cnt += (cl ^ ((cp1x + cp1y) & 1)) * dx1 * dy1;
    if(p2.x > p1.x) cnt += (cl ^ ((cp2x + cp1y) & 1)) * dx2 * dy1;
    if(p2.y > p1.y) cnt += (cl ^ ((cp1x + cp2y) & 1)) * dx1 * dy2;
    if(p2.x > p1.x && p2.y > p1.y) cnt += (cl ^ ((cp2x + cp2y) & 1)) * dx2 * dy2;
    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    ll n, k;
    cin >> n >> k;
    point v1[k], v2[k];
    for(int i = 0; i < k; i++) {
        point p1, p2;
        cin >> p1.x >> p1.y;
        p1.x--; p1.y--;
        cin >> p2.x >> p2.y;
        p2.x--; p2.y--;
        v1[i] = p1; v2[i] = p2;
    }
    ll ans = n * n;
    for(ll D = 1; D <= n; D++) {
        if(n % D) continue;
        ll d = D;
        ll val1 = 0, val2 = 0;
        val1 = black_nums(n / d, n / d, 1) * d * d;
        val2 = black_nums(n / d, n / d, 0) * d * d;
        for(int i = 0; i < k; i++) {
            val1 += (v2[i].x - v1[i].x + 1) * (v2[i].y - v1[i].y + 1) - 2 * func(v1[i], v2[i], d, 1);
            val2 += (v2[i].x - v1[i].x + 1) * (v2[i].y - v1[i].y + 1) - 2 * func(v1[i], v2[i], d, 0);
        }
        ans = min(ans, val1);
        ans = min(ans, val2);
        if(D == 1) continue;
        d = n / D;
        val1 = black_nums(n / d, n / d, 1) * d * d;
        val2 = black_nums(n / d, n / d, 0) * d * d;
        for(int i = 0; i < k; i++) {
            val1 += (v2[i].x - v1[i].x + 1) * (v2[i].y - v1[i].y + 1) - 2 * func(v1[i], v2[i], d, 1);
            val2 += (v2[i].x - v1[i].x + 1) * (v2[i].y - v1[i].y + 1) - 2 * func(v1[i], v2[i], d, 0);
        }
        ans = min(ans, val1);
        ans = min(ans, val2);
    }
    cout << ans;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -