제출 #689594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
689594		YENGOYAN	Chessboard (IZhO18_chessboard)	C++17	70 / 100	550 ms	4252 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& ii : v) {
            ll xx2 = (ii.x2 - 1) / i * i;
            ll xx1 = (ii.x1 - 1) / i * i;
            ll yy2 = (ii.y2 - 1) / i * i;
            ll yy1 = (ii.y1 - 1) / i * i;
            ++xx1, ++yy1;
            ++xx2, ++yy2;
            //cout << xx1 << " " << yy1 << " " << xx2 << " " << yy2 << "\n";
            //if(i == 2) cout << xx1 << " " << yy1 << " " << xx2 << " " << yy2 << "\n";
            if (xx1 < xx2 && yy1 < yy2) {
                ll ynd = (xx2 - xx1 + 1) / i * (yy2 - yy1 + 1) / i;
                ev += (ynd + ((xx1 / i) % 2 == (yy1 / i) % 2)) / 2 * i * i;
                od += (ynd + ((xx1 / i) % 2 != (yy1 / i) % 2)) / 2 * i * i;
                // bajnel vec uxankyan
                // dzax verev
                if (ev_od(ii.x1, ii.y1, i)) {
                    od += (xx1 - ii.x1) * (yy1 - ii.y1);
                }
                else {
                    ev += (xx1 - ii.x1) * (yy1 - ii.y1);
                }
                // aj verev
                if (ev_od(xx2, ii.y1, i)) {
                    od += (yy1 - ii.y1) * (ii.x2 - xx2);
                }
                else {
                    ev += (yy1 - ii.y1) * (ii.x2 - xx2);
                }
                // verev mejtex
                ll h = yy1 - ii.y1;
                if (ev_od(xx1, ii.y1, i)) {
                    ll w = xx2 - xx1, c = w / i;
                    od += (c + 1) / 2 * h * i;
                    ev += c / 2 * h * i;
                }
                else {
                    ll w = xx2 - xx1, c = w / i;
                    od += c / 2 * h * i;
                    ev += (c + 1) / 2 * h * i;
                }
                // mejtex dzax
                ll w = xx1 - ii.x1;
                if (ev_od(ii.x1, yy1, i)) {
                    ll h = yy2 - yy1, c = h / i;
                    od += (c + 1) / 2 * w * i;
                    ev += c / 2 * w * i;
                }
                else {
                    ll h = yy2 - yy1, c = h / i;
                    od += c / 2 * w * i;
                    ev += (c + 1) / 2 * w * i;
                }
                // mejtex aj
                w = ii.x2 - xx2;
                if (ev_od(xx2, yy1, i)) {
                    ll h = yy2 - yy1, c = h / i;
                    od += (c + 1) / 2 * w * i;
                    ev += c / 2 * w * i;
                }
                else {
                    ll h = yy2 - yy1, c = h / i;
                    od += c / 2 * w * i;
                    ev += (c + 1) / 2 * w * i;
                }
                // dzax var
                if (ev_od(ii.x1, yy2, i)) {
                    od += (xx1 - ii.x1) * (ii.y2 - yy2);
                }
                else {
                    ev += (xx1 - ii.x1) * (ii.y2 - yy2);
                }
                // aj var
                if (ev_od(xx2, yy2, i)) {
                    od += (ii.x2 - xx2) * (ii.y2 - yy2);
                }
                else {
                    ev += (ii.x2 - xx2) * (ii.y2 - yy2);
                }
                // var mejtex
                h = ii.y2 - yy2;
                if (ev_od(xx1, yy2, i)) {
                    ll w = xx2 - xx1, c = w / i;
                    od += (c + 1) / 2 * h * i;
                    ev += c / 2 * h * i;
                }
                else {
                    ll w = xx2 - xx1, c = w / i;
                    od += c / 2 * h * i;
                    ev += (c + 1) / 2 * h * i;
                }
            }
            /*
                        6 3
                        1 3 1 3
                        1 4 1 4
                        2 3 2 3
            */
            else if (xx1 >= xx2 && yy1 >= yy2) {
                //if(i == 2) cout << "DEBUG\n";
                // bajnel petq che, patasxany hashvac e
                //cout << "DEBUG\n";
                if (ev_od(ii.x1, ii.y1, i)) {
                    od += (ii.x2 - ii.x1 + 1) * (ii.y2 - ii.y1 + 1);
                }
                else {
                    ev += (ii.x2 - ii.x1 + 1) * (ii.y2 - ii.y1 + 1);
                }
            }
            else if (xx1 >= xx2) {
                // bajnel ireq uxxankyan, verevi u vari masy arandzin, mejtexy arandzin
                // verevi masy
                if (ev_od(ii.x1, ii.y1, i)) {
                    od += (yy1 - ii.y1) * (ii.x2 - ii.x1);
                }
                else {
                    ev += (yy1 - ii.y1) * (ii.x2 - ii.x1);
                }
                // vari masy
                if (ev_od(ii.x1, yy2, i)) {
                    od += (ii.y2 - yy2) * (ii.x2 - ii.x1);
                }
                else {
                    ev += (ii.y2 - yy2) * (ii.x2 - ii.x1);
                }
                // mejtexi masy
                ll h = yy2 - yy1, c = h / i;
                if (ev_od(ii.x1, yy1, i)) {
                    od += (c + 1) / 2 * i * (ii.x2 - ii.x1);
                    ev += c / 2 * i * (ii.x2 - ii.x1);
                }
                else {
                    od += c / 2 * i * (ii.x2 - ii.x1);
                    ev += (c + 1) / 2 * i * (ii.x2 - ii.x1);
                }
            }
            else {
                // bajnel ireq uxxankyan, dzax u aj masy arandzin, mejtexy arandzin
                // dzax masy
                if (ev_od(ii.x1, ii.y1, i)) {
                    od += (ii.x2 - ii.x1) * (ii.y2 - ii.y1);
                }
                else {
                    ev += (ii.x2 - ii.x1) * (ii.y2 - ii.y1);
                }
                // aj masy
                if (ev_od(xx2, ii.y1, i)) {
                    od += (ii.x2 - xx2) * (ii.y2 - ii.y1);
                }
                else {
                    ev += (ii.x2 - xx2) * (ii.y2 - ii.y1);
                }
                // mejtexi masy
                ll w = xx2 - xx1, c = w / i;
                if (ev_od(xx1, ii.y1, i)) {
                    od += (c + 1) / 2 * i * (ii.y2 - ii.y1);
                    ev += c / 2 * i * (ii.y2 - ii.y1);
                }
                else {
                    od += c / 2 * i * (ii.y2 - ii.y1);
                    ev += (c + 1) / 2 * i * (ii.y2 - ii.y1);
                }
            }
        }
        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;
        ans = min({ ans, a, b });
    }
    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