Submission #683128

#	Time	Username	Problem	Language	Result	Execution time	Memory
683128		phoenix	Chessboard (IZhO18_chessboard)	C++17	100 / 100	1876 ms	5804 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;
    // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
    // cout << dx1 << ' ' << dy1 << ' ' << dx2 << ' ' << dy2 << '\n';
    ll cnt = 0;
    cnt += black_nums((x2 - x1 + 1) / d, (y2 - y1 + 1) / d, (cl ^ ((x1 / d + y1 / d) % 2))) * d * d;
    cnt += black_nums((x2 - x1 + 1) / d, 1, (cl ^ ((x1 / d + p1.y / d) % 2))) * dy1 * d;
    cnt += black_nums((x2 - x1 + 1) / d, 1, (cl ^ ((x1 / d + p2.y / d) % 2))) * dy2 * d;
    cnt += black_nums(1, (y2 - y1 + 1) / d, (cl ^ ((p1.x / d + y1 / d) % 2))) * dx1 * d;
    cnt += black_nums(1, (y2 - y1 + 1) / d, (cl ^ ((p2.x / d + y1 / d) % 2))) * dx2 * d;
    cnt += (cl ^ ((p1.x / d + p1.y / d) % 2)) * dx1 * dy1;
    if(p2.x > p1.x) cnt += (cl ^ ((p2.x / d + p1.y / d) % 2)) * dx2 * dy1;
    if(p2.y > p1.y) cnt += (cl ^ ((p1.x / d + p2.y / d) % 2)) * dx1 * dy2;
    if(p2.x > p1.x && p2.y > p1.y) cnt += (cl ^ ((p2.x / d + p2.y / d) % 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: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 30 / 30