Submission #1128668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128668		Zero_OP	Chessboard (IZhO18_chessboard)	C++20	70 / 100	410 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;
}

#define on_debug true

void output(string s){
    if(on_debug) cout << s << '\n';
}

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

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;
        }
    }

//    ll backup = 0;
    for(int i = 0; i < K; ++i){
        int lb = (L[i] / d), rb = (R[i] / d);
        int rl = (L[i] % d), rr = (R[i] % d);

        int sb = (U[i] / d), tb = (B[i] / d);
        int rs = (U[i] % d), rt = (B[i] % d);

//        cout << result - backup << '\n';
//        backup = result;

        if(lb == rb){
            if(sb == tb){
//                output("case 1.1\n");
                if(check(lb, sb, add)) result += area(L[i], U[i], R[i], B[i]); //wrong color
                else result -= area(L[i], U[i], R[i], B[i]); //correct color
            } else{
//                output("case 1.2\n");
                //half left part
                if(check(lb, sb, add)) result += area(L[i], U[i], R[i], (sb + 1) * d - 1);
                else result -= area(L[i], U[i], R[i], (sb + 1) * d - 1);

                //half right part
                if(check(lb, tb, add)) result += area(L[i], tb * d, R[i], B[i]);
                else result -= area(L[i], tb * d, R[i], B[i]);

                //between blocks
                int between = (tb - sb - 1);
                if(between > 0){
                    int between_odd = (between / 2);
                    int between_even = (between / 2);
                    if(between & 1){
                        if((sb + 1) & 1) ++between_odd;
                        else ++between_even;
                    }

                    //(lb + parity)
                    if(check(lb, 1, add)){
                        result += area(L[i], 1, B[i], d) * between_odd;
                        result -= area(L[i], 1, B[i], d) * between_even;
                    } else{
                        result -= area(L[i], 1, B[i], d) * between_odd;
                        result += area(L[i], 1, B[i], d) * between_even;
                    }
                }
            }
        } else{
            if(sb == tb){
//                output("case 2.1\n");
                //half left
                if(check(lb, sb, add)) result += area(L[i], U[i], (lb + 1) * d - 1, B[i]);
                else result -= area(L[i], U[i], (lb + 1) * d - 1, B[i]);

                //half right
                if(check(rb, sb, add)) result += area(rb * d, U[i], R[i], B[i]);
                else result -= area(rb * d, U[i], R[i], B[i]);

                //between blocks
                int between = (rb - lb - 1);
                if(between > 0){
                    int between_odd = (between / 2);
                    int between_even = (between / 2);
                    if(between & 1){
                        if((lb + 1) & 1) ++between_odd;
                        else ++between_even;
                    }

                    if(check(sb, 1, add)){
                        result += area(1, U[i], d, B[i]) * between_odd;
                        result -= area(1, U[i], d, B[i]) * between_even;
                    } else{
                        result -= area(1, U[i], d, B[i]) * between_odd;
                        result += area(1, U[i], d, B[i]) * between_even;
                    }
                }
            } else{
//                output("case 2.2\n");
                ///4 corners blocks
                //upper-left
                if(check(lb, sb, add)) result += area(L[i], U[i], (lb + 1) * d - 1, (sb + 1) * d - 1);
                else result -= area(L[i], U[i], (lb + 1) * d - 1, (sb + 1) * d - 1);

                //upper-right
                if(check(lb, tb, add)) result += area(L[i], tb * d, (lb + 1) * d - 1, B[i]);
                else result -= area(L[i], tb * d, (lb + 1) * d - 1, B[i]);

                //lower-left
                if(check(rb, sb, add)) result += area(rb * d, U[i], R[i], (sb + 1) * d - 1);
                else result -= area(rb * d, U[i], R[i], (sb + 1) * d - 1);

                //lower-right
                if(check(rb, tb, add)) result += area(rb * d, tb * d, R[i], B[i]);
                else result -= area(rb * d, tb * d, R[i], B[i]);

                ///4 Sides
                if(rb - lb - 1 > 0){
                    int between = rb - lb - 1;
                    int between_odd = (between / 2);
                    int between_even = (between) / 2;
                    if(between & 1){
                        if((lb + 1) & 1) ++between_odd;
                        else ++between_even;
                    }

                    //left side
                    if(check(sb, 1, add)){
                        result += area(1, U[i], d, (sb + 1) * d - 1) * between_odd;
                        result -= area(1, U[i], d, (sb + 1) * d - 1) * between_even;
                    } else{
                        result -= area(1, U[i], d, (sb + 1) * d - 1) * between_odd;
                        result += area(1, U[i], d, (sb + 1) * d - 1) * between_even;
                    }

                    //right side
                    if(check(tb, 1, add)){
                        result += area(1, tb * d, d, B[i]) * between_odd;
                        result -= area(1, tb * d, d, B[i]) * between_even;
                    } else{
                        result -= area(1, tb * d, d, B[i]) * between_odd;
                        result += area(1, tb * d, d, B[i]) * between_even;
                    }
                }

                if(tb - sb - 1 > 0){
                    int between = (tb - sb - 1);
                    int between_odd = (between / 2);
                    int between_even = (between / 2);
                    if(between & 1){
                        if((sb + 1) & 1) ++between_odd;
                        else ++between_even;
                    }

                    //upper side
                    if(check(lb, 1, add)){
                        result += area(L[i], 1, (lb + 1) * d - 1, d) * between_odd;
                        result -= area(L[i], 1, (lb + 1) * d - 1, d) * between_even;
                    } else{
                        result -= area(L[i], 1, (lb + 1) * d - 1, d) * between_odd;
                        result += area(L[i], 1, (lb + 1) * d - 1, d) * between_even;
                    }

                    //lower side
                    if(check(rb, 1, add)){
                        result += area(rb * d, 1, R[i], d) * between_odd;
                        result -= area(rb * d, 1, R[i], d) * between_even;
                    } else{
                        result -= area(rb * d, 1, R[i], d) * between_odd;
                        result += area(rb * d, 1, R[i], d) * between_even;
                    }
                }

                //between - between
                if(rb - lb - 1 > 0 && tb - sb - 1 > 0){
                    a[0] = a[1] = (rb - lb - 1) / 2;
                    b[0] = b[1] = (tb - sb - 1) / 2;
                    if((rb - lb - 1) & 1){
                        if((lb + 1) & 1) ++a[1];
                        else ++a[0];
                    }

                    if((tb - sb - 1) & 1){
                        if((sb + 1) & 1) ++b[1];
                        else ++b[0];
                    }

                    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){
    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:278:5: note: in expansion of macro 'file'
  278 |     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:278:5: note: in expansion of macro 'file'
  278 |     file("B");
      |     ^~~~

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