Submission #1269190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269190		BuiDucManh123	Chessboard (IZhO18_chessboard)	C++20	100 / 100	169 ms	624 KiB

chessboard

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define taskname ""
#define ld long double
using namespace std;
#define int ll
int a0[100009], a1[100009];
int pre(int i, int x) {
    if (i <= 0) return 0;
    int t = (i - 1) / x;
    int r = i - t * x;
    int res = (t % 2 ? x : 0) + ((t % 2 == 0) ? r : -r);
    return res;
}

int sumpre(int l, int r, int x) {
    if (r < l) return 0;
    return pre(r, x) - pre(l - 1, x);
}
signed main() {
    if (fopen(taskname".inp","r")) {
        freopen(taskname".inp","r",stdin);
        freopen(taskname".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> dv;
    for(int i = 1; i < n; i++){
        if(n % i == 0){
            dv.pb(i);
        }
    }
    sort(dv.begin(), dv.end());
    int sum = 0;
    while(k--){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int area = (x2 - x1 + 1) * (y2 - y1 + 1);
        sum += area;
        for(int s : dv){
            int sx = sumpre(x1, x2, s);
            int sy = sumpre(y1, y2, s);
            int black = (area + sx * sy) / 2;
            a0[s] += black;
            a1[s] += (area - black);
        }
    }
    int res = 1e18;
    for (int s : dv) {
        int c0 = ((n / s) * (n / s) + 1) / 2;
        int c1 = (n / s) * (n / s) - ((n / s) * (n / s) + 1) / 2;
        int r0 = c0 * s * s + sum - 2 * a0[s];
        int r1 = c1 * s * s + sum - 2 * a1[s];
        res = min(res, min(r0, r1));
    }
    cout << res;
    return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(taskname".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
chessboard.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(taskname".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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