Submission #162803

#	Time	Username	Problem	Language	Result	Execution time	Memory
162803		mrboorger	Chessboard (IZhO18_chessboard)	C++17	70 / 100	721 ms	5880 KiB

chessboard

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define sqr(x) (x) * (x)

using namespace std;
using namespace __gnu_pbds;

ll n, k;
vector <pair <pair <ll, ll>, pair <ll, ll>>> a;
ll ans;
void solve(ll l)
{
    ll cnt = sqr(((n + l) / (2 * l)) * l);
    cnt += sqr((n / (2 * l)) * l);
    {
        ll ot = cnt;
        for(int i = 0; i < k; ++i)
        {
            ll x = a[i].F.F;
            ll y = a[i].F.S;
            if (((((x + l - 1) / l) % 2) ^ (((y + l - 1) / l) % 2)) == 0) --ot;
                else ++ot;
        }
        ans = min(ans, ot);
    }
    {
        ll ot = n * n - cnt;
        for(int i = 0; i < k; ++i)
        {
            int x = a[i].F.F;
            int y = a[i].F.S;
            if (((((x + l - 1) / l) % 2) ^ (((y + l - 1) / l) % 2)) == 1) --ot;
                else ++ot;
        }
        ans = min(ans, ot);
    }
    return;
}

int main()
{
#ifdef LOCAL
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    a.resize(k);
    for(int i = 0; i < k; ++i)
    {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        a[i] = {{x1, y1}, {x2, y2}};
    }
    ans = n * n;
    ll i;
    for(i = 1; i * i < n; ++i)
    {
        if (n % i == 0)
        {
            solve(i);
            if (i > 1) solve(n / i);
        }
    }
    if (i * i == n) solve(i);
    cout << ans;
    return 0;
}

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