Submission #378526

#	Time	Username	Problem	Language	Result	Execution time	Memory
378526		joylintp	Chessboard (IZhO18_chessboard)	C++17	70 / 100	247 ms	1132 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;

//#pragma gcc optimize("Ofast,unroll-loops")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double
#define MP make_pair
#define F first
#define S second
#define MOD 1000000007

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, K;
    cin >> N >> K;

    vector<pair<int, int>> B(K);
    for (auto &p : B)
        cin >> p.F >> p.S >> p.F >> p.S, p.F--, p.S--;

    vector<int> fac = {1};
    for (int i = 2; i * i <= N; i++)
        if (N % i == 0)
        {
            if (i * i != N)
                fac.push_back(i);
            fac.push_back(N / i);
        }

    long long ans = 9e18;
    for (int x : fac)
    {
        long long wc = (long long)(N / x) * (N / x) / 2 * x * x, bc = (long long)N * N - wc;
        for (auto p : B)
            if ((p.F / x + p.S / x) % 2)
                wc--, bc++;
            else
                wc++, bc--;

        ans = min({ans, wc, bc});
    }
    cout << ans << '\n';

    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