Submission #651941

#	Time	Username	Problem	Language	Result	Execution time	Memory
651941		vovik	Chessboard (IZhO18_chessboard)	C++17	100 / 100	935 ms	10388 KiB

chessboard

//I wrote this code 4 u today
#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;
 
#define int ll
 
ll get(int x, int y, int s, int c) {
    return (ll)x * s * (y & 1) * ((c == 0) - (c == 1));
}
 
ll get(int x, int y, int s) {
    int a = x / s, b = y / s;
    ll ans = 0;
    if (((a & 1) + (b & 1)) >> 1) ans += s * s;
    if ((a & 1) != (b & 1)) ans -= (x % s) * (y % s);
    else ans += (x % s) * (y % s);
    ans += get(x % s, b, s, a & 1);
    ans += get(y % s, a, s, b & 1);
 
//    //[0; y], x % s;
//    {
//        ll f = 0;
//        f += (y / (2 * s)) * s;
//        if (y % (2 * s) > s) f += y % (2 * s) - s;
//        f *= x % s;
//        if (a & 1) f = (ll) (x % s) * y - f;
//        ans += f;
//    }
//    {
//        ll f = ((a * s) / (2 * s)) * s;
//        f *= y % s;
//        if (b & 1) f = (ll) (y % s) * (a * s) - f;
//        ans += f;
//    }
    return ans;
}
 
ll get(pair<int, int> x, int s) {
    return get(x.first, x.second, s);
}
 
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 (int 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], s) - get(v[1], s) - get(v[2], s) + get(v[3], s);
        }
        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