Submission #1128671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128671		Zero_OP	Chessboard (IZhO18_chessboard)	C++20	100 / 100	1815 ms	2008 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int MAX = 1e5 + 5;

#define x1 __x1
#define y1 __y1
#define x2 __x2
#define y2 __y2

int N, K, L[MAX], U[MAX], R[MAX], B[MAX];

//blocks size d are numbered from 0 to (N / d) - 1
//the cells are also numbered from (0, 0) to (N - 1, N - 1)
//block of the cell :
//          block of x : x / d
//          block of y : y / d


ll area(int L, int U, int R, int B){
    return 1LL * (R - L + 1) * (B - U + 1);
}

//ll solve_in_block(int bx, int by, int L, int U, int R, int B){
//
//}
//
//ll solve_half_head_in_block(int bx, int by, int L, int U, int R, int B){
//
//}

bool check(int x, int y, int z){
    return ((x + y) & 1) == z;
}

int A[2], a[2], b[2];

ll rec(int x, int y, int d, bool add){
    if(x < 0 || y < 0) return 0;
    ll result = 0;

    a[0] = a[1] = 0;
    b[0] = b[1] = 0;

    int bx = (x / d), by = (y / d);
    int lbx = bx * d, lby = by * d;

    if(check(bx, by, add)) result += area(lbx, lby, x, y);
    else result -= area(lbx, lby, x, y);

    if(bx > 0){ //right side
        int e = (bx + 1) / 2;
        int o = (bx) / 2;

        if(check(0, by, add)){
            result += area(1, lby, d, y) * e;
            result -= area(1, lby, d, y) * o;
        } else{
            result -= area(1, lby, d, y) * e;
            result += area(1, lby, d, y) * o;
        }
    }

    if(by > 0){ //down side
        int e = (by + 1) / 2;
        int o = (by) / 2;
        if(check(0, bx, add)){
            result += area(lbx, 1, x, d) * e;
            result -= area(lbx, 1, x, d) * o;
        } else{
            result -= area(lbx, 1, x, d) * e;
            result += area(lbx, 1, x, d) * o;
        }
    }

    if(bx > 0 && by > 0){ //between - between
        a[0] = (bx + 1) /2;
        a[1] = (bx) / 2;
        b[0] = (by + 1) / 2;
        b[1] = (by) / 2;
        for(int i = 0; i < 2; ++i){
            for(int j = 0; j < 2; ++j){
                if(check(i, j, add)) result += area(1, 1, d, d) * a[i] * b[j];
                else result -= area(1, 1, d, d) * a[i] * b[j];
            }
        }
    }
    return result;
}

ll solve(int d, bool add){
    //(block of x) + (block of y) % 2 = add => black block

    A[0] = A[1] = (N / d) / 2;
    if((N / d) & 1) ++A[0];

    ll result = 0;
    for(int i = 0; i < 2; ++i){
        for(int j = 0; j < 2; ++j){
            if(check(i, j, !add)) result += 1LL * A[i] * A[j] * d * d;
        }
    }

    for(int i = 0; i < K; ++i){
        result += rec(R[i], B[i], d, add) - rec(L[i] - 1, B[i], d, add) - rec(R[i], U[i] - 1, d, add) + rec(L[i] - 1, U[i] - 1, d, add);
    }
    return result;
}

ll solve(int d){
    return min(solve(d, 0), solve(d, 1));
}

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

    file("B");

    cin >> N >> K;
    for(int i = 0; i < K; ++i){
        cin >> L[i] >> U[i] >> R[i] >> B[i];
        --L[i], --U[i], --R[i], --B[i];
    }

    ll ans = 1e18;
    for(int i = 1; i * i <= N; ++i){
        if(N % i == 0){
            ans = min(ans, solve(i));
            if(N / i != i && i > 1) ans = min(ans, solve(N / i));
        }
    }

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:10:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
chessboard.cpp:150:5: note: in expansion of macro 'file'
  150 |     file("B");
      |     ^~~~
chessboard.cpp:10:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
chessboard.cpp:150:5: note: in expansion of macro 'file'
  150 |     file("B");
      |     ^~~~

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