Submission #683127

#	Time	Username	Problem	Language	Result	Execution time	Memory
683127		phoenix	Chessboard (IZhO18_chessboard)	C++17	8 / 100	28 ms	2688 KiB

chessboard

#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 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);
    // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
    if((dx1 || dx2) && p1.x / d == p2.x / d) dx1 = p2.x - p1.x + 1, dx2 = 0; 
    x1 += dx1; x2 -= dx2;
    if((dx1 || dx2) && p1.y / d == p2.y / d) dy1 = p2.y - p1.y + 1, dy2 = 0; 
    y1 += dy1; y2 -= dy2;
    ll cx1 = x1 / d, cy1 = y1 / d, cp1y = p1.y / d, cp1x = p1.x / d, cp2x = p2.x / d, cp2y = p2.y / d;
    ll cnt = 0;
    cnt += black_nums(cp2x - cx1, cp2y - cy1, (cl ^ ((cx1 + cy1) % 2))) * d * d;
    cnt += black_nums(cp2x - cx1, 1, (cl ^ ((cx1 + cp1y) % 2))) * dy1 * d;
    cnt += black_nums(cp2x - cx1, 1, (cl ^ ((cx1 + cp2y) % 2))) * dy2 * d;
    cnt += black_nums(1, cp2y - cy1, (cl ^ ((cp1x + cy1) % 2))) * dx1 * d;
    cnt += black_nums(1, cp2y - cy1, (cl ^ ((cp2x + cy1) % 2))) * dx2 * d;
    cnt += (cl ^ ((cp1x + cp1y) % 2)) * dx1 * dy1;
    if(p2.x > p1.x) cnt += (cl ^ ((cp2x + cp1y) % 2)) * dx2 * dy1;
    if(p2.y > p1.y) cnt += (cl ^ ((cp1x + cp2y) % 2)) * dx1 * dy2;
    if(p2.x > p1.x && p2.y > p1.y) cnt += (cl ^ ((cp2x + cp2y) % 2)) * dx2 * dy2;
    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    ll n, k;
    cin >> n >> k;
    vector<pair<point, point>> v;
    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 * 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: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30