Submission #689617

#	Time	Username	Problem	Language	Result	Execution time	Memory
689617		YENGOYAN	Chessboard (IZhO18_chessboard)	C++17	70 / 100	617 ms	4184 KiB

chessboard

/*
        //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
        \\                                    //
        //  271828___182845__904523__53602__  \\
        \\  87___47____13______52____66__24_  //
        //  97___75____72______47____09___36  \\
        \\  999595_____74______96____69___67  //
        //  62___77____24______07____66__30_  \\
        \\  35___35____47______59____45713__  //
        //                                    \\
        \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
                                                    */

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>

using namespace std;
using ll = long long;
const int N = 3e5 + 5;
const ll mod = 1e9 + 7, inf = 1e18;

struct rec {
    ll x1, y1, x2, y2;
};

bool ev_od(ll x, ll y, ll side) {
    ll xx = (x + side - 1) / side, yy = (y + side - 1) / side;
    if (xx % 2 == yy % 2) return 0;
    return 1;
}

void solve() {
    ll n, k; cin >> n >> k;
    vector<rec> v(k);
    for (int i = 0; i < k; ++i) {
        cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2;
    }
    ll ans = n * n;
    for (int i = 1; i < n; ++i) {
        if (n % i) continue;
        ll od = 0, ev = 0;
        for (rec& j : v) {
            // (j.x2 - j.x1 + 1) X (j.y2 - j.y1 + 1)
            ll len_x = j.x2 - j.x1 + 1, len_y = j.y2 - j.y1 + 1;
            ll toshni_x = len_x / i * i, toshni_y = len_y / i * i;
            if (ev_od(j.x1, j.y1, i)) {
                //cout << "TAMAMA?\n";
                ll obshi = toshni_x / i * toshni_y / i;
                od += (obshi + 1) / 2 * i * i;
                ev += obshi / 2 * i * i;
                //cout << obshi << "\n";
            }
            else {
                //cout << "TAMAMA?\n";
                ll obshi = toshni_x / i * toshni_y / i;
                od += obshi / 2 * i * i;
                ev += (obshi + 1) / 2 * i * i;
                //cout << obshi << "\n";
            }
            //cout << od << " " << ev << "\n";
            //break;
            ll new_x = j.x1 + toshni_x - 1, new_y = j.y1 + toshni_y - 1;
            //cout << new_x << " " << new_y << "\n";
            ll w = j.x2 - new_x, h = new_y - j.y1;
            ll c = h / i;
            if (ev_od(new_x + 1, j.y1, i)) {
                od += (c + 1) / 2 * w * i;
                ev += c / 2 * w * i;
            }
            else {
                od += c / 2 * w * i;
                ev += (c + 1) / 2 * w * i;
            }
            h = j.y2 - new_y, w = new_x - j.x1;
            c = w / i;
            if (ev_od(j.x1, new_y + 1, i)) {
                od += (c + 1) / 2 * h * i;
                ev += c / 2 * h * i;
            }
            else {
                od += c / 2 * h * i;
                ev += (c + 1) / 2 * h * i;
            }
            if (ev_od(new_x + 1, new_y + 1, i)) {
                od += (j.x2 - new_x) * (j.y2 - new_y);
            }
            else {
                ev += (j.x2 - new_x) * (j.y2 - new_y);
            }
            //cout << od << " " << ev << "\n";

        }
        /*ll edge = n / i, c = (edge * edge + 1) / 2;
        ll a = od + c * i * i - ev;
        c = edge * edge / 2;
        ll b = ev + c * i * i - od;
        cout << a << " " << b << " ";
        ans = min({ ans, a, b });*/
        //swap(ev, od);
        //cout << od << " " << ev << "\n";
        ll edge = n / i;
        ll yndhanur_zuyg = (edge * edge + 1) / 2 * i * i, yndhanur_kent = (edge * edge) / 2 * i * i;
        //cout << od << " " << ev << "\n";
        //cout << yndhanur_kent << " " << yndhanur_zuyg << "\n";
        ll bl = yndhanur_zuyg - ev + od;
        ans = min(ans, bl);
        ll wh = yndhanur_kent - od + ev;
        ans = min(ans, wh);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    //int t; cin >> t;
    //while (t--)	
    solve();
}

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