Submission #90329

#	Time	Username	Problem	Language	Result	Execution time	Memory
90329		adlet	Chessboard (IZhO18_chessboard)	C++17	70 / 100	1797 ms	3840 KiB

chessboard

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;

typedef long long ll;

#define int ll
#define y1 sda

const int N = 1e5 + 5;
const ll INF = 2e18;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);

int n, k;

ll ans = INF, k_area;

vector < int > v;

ll get(int x, int y, int xx, int yy, int len) {
    if (min({x, xx, y, yy}) < 0 || x > xx || y > yy)
        return 0;
    int f = ((x / len) % 2 == (y / len) % 2);
    x = (xx - x + 1) / len;
    y = (yy - y + 1) / len;
    ll num = (x * y) / 2;
    if (f) {
        num += ((x * y) % 2);
    }
    return num * len * len;
}

ll get_corner(int x, int y, int xx, int yy, int len) {
    if (min({x, xx, y, yy}) < 0 || x > xx || y > yy)
        return 0;
    int f = (((x / len) % 2) == ((y / len) % 2));
    x = (xx - x + 1);
    y = (yy - y + 1);
    ll num = (x * y) * f;
    return num;
}

int left(int l, int len) {
    return ((l + (len - 1)) / len) * len;
}

int right(int r, int len) {
    return (((r + 1) / len) * len) - 1;
}

ll get_sidex(int x, int y, int xx, int yy, int len) {
    if (min({x, xx, y, yy}) < 0 || x > xx || y > yy)
        return 0;
    int f = ((x / len) % 2) == ((y / len) % 2);
    y = yy - y + 1;
    x = (xx - x + 1) / len;
    ll num = (x / 2) + f * (x % 2);
    return num * y * len;
}

ll get_sidey(int x, int y, int xx, int yy, int len) {
    if (x > xx || y > yy)
        return 0;
    int f = ((x / len) % 2) == ((y / len) % 2);
    y = (yy - y + 1) / len;
    x = xx - x + 1;
    ll num = (y / 2) + f * (y % 2);
    return num * x * len;
}

ll get_one(int x, int y, int len) {
    return (((x / len) % 2) == ((y / len) % 2));
}

int x1[N], y1[N], x2[N], y2[N];

main() {
    cin >> n >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
        x1[i]--;
        y1[i]--;
        x2[i]--;
        y2[i]--;
        k_area += (y2[i] - y1[i] + 1) * (x2[i] - x1[i] + 1);
    }
    v.push_back(1);
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (n / i != i) {
                v.push_back(n / i);
            }
        }
    }
//    cout << k_area << "\n";
    for (int i : v) {
        int m = n / i, cnt_black = 0, cnt_white = 0;
        ll black = (((m * m) / 2) + ((m * m) % 2)) * (i * 1ll * i);
        ll white = (n * 1ll * n) - black;
//        cout << i << " " << m << " " << black << " " << white << "\n";
        for (int j = 1; j <= k; ++j) {
            if (x1[j] == x2[j] && y1[j] == y2[j]) {
                cnt_black += get_one(x1[j], y1[j], i);
            } else {
                int px1 = -1, px2 = -1, py1 = -1, py2 = -1;
                ll center_black = 0, corner_black = 0, side_black = 0;
                px1 = left(x1[j], i);
                py1 = left(y1[j], i);
                px2 = right(x2[j], i);
                py2 = right(y2[j], i);
                center_black = get(px1, py1, px2, py2, i);
                corner_black = get_corner(x1[j], y1[j], px1 - 1, py1 - 1, i) +
                               get_corner(px2 + 1, y1[j], x2[j], py1 - 1, i) +
                               get_corner(x1[j], py2 + 1, px1 - 1, y2[j], i) +
                               get_corner(px2 + 1, py2 + 1, x2[j], y2[j], i);
                side_black = get_sidex(px1, y1[j], px2, py1 - 1, i) + get_sidex(px1, py2 + 1, px2, y2[j], i) +
                             get_sidey(x1[j], py1, px1 - 1, py2, i) + get_sidey(px2 + 1, py1, x2[j], py2, i);
                cnt_black += center_black + corner_black + side_black;
//                cout << "\t" << j << " " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
//                cout << "\t\t" << center_black << " " << corner_black << " " << side_black << "\n";
            }
        }
        cnt_white = k_area - cnt_black;
        ll fx = (black - cnt_black) + cnt_white;
        ll fy = (white - cnt_white) + cnt_black;
//        cout << cnt_black << " " << cnt_white << " " << fx << " " << fy << "\n\n";
        ans = min(ans, min(fx, fy));
    }
    cout << ans;
}

Compilation message (stderr)

chessboard.cpp:81:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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