제출 #523568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523568		RaresFelix	Chessboard (IZhO18_chessboard)	C++17	39 / 100	483 ms	2544 KiB

chessboard

#include <bits/stdc++.h>
#define MN 107171

using namespace std;
using ll = long long;
int n, k;
vector<tuple<int, int, int, int>> R;

ll calc(ll a, ll b, ll l) {
    if(a % l == 0 && b % l == 0)
        return ((a / l) * (b / l) + 1) / 2 * l * l;
    if(a % l) {
        ll nrseg;
        if(a / l % 2ll == 0) {
            if(b % (2ll * l) <= l) nrseg = (b / (2ll * l)) * l + b % (2 * l);
            else nrseg =  (b / (2ll * l) + 1) * l;
        } else {
            if(b % (2ll * l) <= l) nrseg = (b / (2ll * l)) * l;
            else nrseg = (b / (2ll * l) - 1) * l + b % (2 * l);
        }
        return calc(a - (a % l), b, l) + (a % l) * nrseg;
    }
    return calc(b, a, l);
}
ll sol(int l) {
    ll arie = ((n / l) * (n / l) + 1) / 2 * l * l, selec, hash;
    for(auto [a, b, c, d] : R) {
        selec = calc(c, d, l) + calc(a-1, b-1, l) - calc(c, b-1, l) - calc(a-1, d, l);
        arie += (c - a + 1) * (d - b + 1) - 2 * selec;
    }
    return min(arie, 1ll * n * n - arie);
}
int main() {
    cin >> n >> k;
    for(int i = 1, a, b, c, d; i <= k; ++i)
        cin >> a >> b >> c >> d, R.emplace_back(a, b, c, d);
    ll re = LLONG_MAX;
    for(int i = 1; i < n; ++i)
        if(n % i == 0) re = min(re, sol(i));
    cout << re << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp: In function 'll sol(int)':
chessboard.cpp:26:59: warning: unused variable 'hash' [-Wunused-variable]
   26 |     ll arie = ((n / l) * (n / l) + 1) / 2 * l * l, selec, hash;
      |                                                           ^~~~

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