제출 #1132047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132047		tredsused70	Chessboard (IZhO18_chessboard)	C++20	100 / 100	610 ms	3400 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;
    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;
}

/*
8 2
1 6 1 6
6 1 6 1
*/

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