Submission #1132042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132042		tredsused70	Chessboard (IZhO18_chessboard)	C++20	16 / 100	20 ms	3140 KiB

chessboard

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mpr make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax = 100011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300;
const ll infll = 4000000000000000000;
const ld eps = 1e-9;

ll calc1(ll x, ll y, ll side) {
    if(x <= 0 || y <= 0)
        return 0;
    ll wholex = x / side;
    ll wholey = y / side;
    ll ans = (wholex * wholey + 1) / 2 * side * side;
    ll width = x - wholex * side;
    ll length = y;
    ll t = length / (2 * side) * side + min(side, length % (2 * side));
    if(wholex % 2 == 1)
        t = length - t;
    ans += t * width;
    if(ans != t * width) {
        width = y - wholey * side;
        length = wholex * side;
        t = length / (2 * side) * side + min(side, length % (2 * side));
        if(wholey % 2 == 1)
            t = length - t;
        ans += t * width;
    }
    //cout << x << " " << y << " " << side << " " << ans << " x y side ans\n";
    return ans;
}

ll calc(ll x1, ll y1, ll x2, ll y2, ll side) {
    ll ans = calc1(x2, y2, side) - calc1(x2, y1 - 1, side) - calc1(x1 - 1, y2, side) + calc1(x1 - 1, y1 - 1, side);
    //cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << side << " " << ans << " rect side ans\n";
    return ans;
}

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<array<ll, 4>> rect(k);
    ll blackeven, totaleven, totalblack = 0, ans = n * n;
    for(int i = 0; i < k; i++) {
        cin >> rect[i][0] >> rect[i][1] >> rect[i][2] >> rect[i][3];
        totalblack += (rect[i][2] - rect[i][0] + 1) * (rect[i][3] - rect[i][1] + 1);
    }
    //cout << totalblack << " totalblack\n";
    for(ll j = 1; j < n; j++) {
        if(n % j != 0)
            continue;
        blackeven = 0;
        for(int i = 0; i < k; i++)
            blackeven += calc(rect[i][0], rect[i][1], rect[i][2], rect[i][3], j);
        //cout << blackeven << " blackeven\n";
        totaleven = n * n;
        if((n / j) % 2 == 1)
            totaleven += j * j;
        totaleven /= 2;
        //cout << totaleven << " totaleven\n";
        ans = min(ans, totaleven - 2 * blackeven + totalblack);
        ans = min(ans, n * n - totaleven + 2 * blackeven - totalblack);
    }
    cout << ans << "\n";
    return ;
}

int main()
{
    //freopen("wormsort.in","r",stdin);
    //freopen("wormsort.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    srand(8713);
    //init();
    int t = 1;
    //cin >> t;
    //int t_ = t;
    //t = rdi();
    while(t--) {
        //cout << "Case #" << t_ - t << ": ";
        solve();
    }
    //flush();
    return 0;
}

/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/

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