Submission #651940

#	Time	Username	Problem	Language	Result	Execution time	Memory
651940		vovik	Chessboard (IZhO18_chessboard)	C++17	100 / 100	790 ms	9684 KiB

chessboard

#include <bits/stdc++.h>

#define vc vector

#define nd node*
#define pnd pair<nd, nd>

using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

int s;

ll get(int x, int y, int c) {
    return (ll)x * s * (y & 1) * ((c == 0) - (c == 1));
}

ll get(int x, int y) {
    int a = x / s, b = y / s;
    ll ans = 0;
    if (((a & 1) + (b & 1)) >> 1) ans += (ll)s * s;
    if ((a & 1) != (b & 1)) ans -= (ll)(x % s) * (y % s);
    else ans += (ll)(x % s) * (y % s);
    ans += get(x % s, b, a & 1);
    ans += get(y % s, a, b & 1);
    return ans;
}

int32_t main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vc<vc<pair<int, int>>> tr(k, vc<pair<int, int>>(4));
    for (auto &i: tr) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        i = {
                {c, d},
                {a - 1, d},
                {c, b - 1},
                {a - 1, b - 1}
        };
    }
    ll ans = INF;
    for (s = 1; s < n; ++s) {
        if (n % s) continue;
        ll sm = ((ll)n * n / s / s) / 2 * s * s;
        for (auto &v : tr) {
            sm += get(v[0].first, v[0].second) - get(v[1].first, v[1].second) -
                  get(v[2].first, v[2].second) + get(v[3].first, v[3].second);
        }
        ans = min(ans, min(sm, (ll)n * n - sm));
    }
    cout << ans << '\n';
}

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