제출 #1269091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269091		nathan4690	Chessboard (IZhO18_chessboard)	C++20	100 / 100	426 ms	3568 KiB

chessboard

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
#define int long long
using namespace std;
const ll maxn=1e6+5, inf=1e18;

struct Rect{
    int x1, y1, x2, y2;
};

int n, k;
ll ans;
Rect a[maxn];

int CC(int i, int j, int c00){
    return (int)((i + j) % 2 == 1) ^ c00;
}

ll calc(int sz, int x1, int x2, int y1, int y2, int c00){
    if(x1 > x2 || y1 > y2) return 0;
    int li = x1 / sz, ri = x2 / sz;
    int lj = y1 / sz, rj = y2 / sz;
    int col = CC(li, lj, c00);
    ll cur = 0;
    if(li == ri){
        if(lj == rj){
            if(!col) cur += 1LL * (x2 - x1 + 1) * (y2 - y1 + 1);
            else cur -= 1LL * (x2 - x1 + 1) * (y2 - y1 + 1);
        }else{
            ll yleft = (lj + 1) * sz - 1;
            if(col){
                cur -= (x2 - x1 + 1) * (yleft - y1 + 1);
            }else{
                cur += (x2 - x1 + 1) * (yleft - y1 + 1);
            }
            if((rj - lj + 1) % 2 != 0){
                if(col) cur += 1LL * (x2 - x1 + 1) * sz;
                else cur -= 1LL * (x2 - x1 + 1) * sz;
            }
            ll yright = rj * sz;
            if(CC(ri, rj, c00)){
                cur -= (x2 - x1 + 1) * (y2 - yright + 1);
            }else{
                cur += (x2 - x1 + 1) * (y2 - yright + 1);
            }
        }
        return cur;
    }
    if(lj == rj){
        ll xtop = (li + 1) * sz - 1;
        if(col){
            cur -= (xtop - x1 + 1) * (y2 - y1 + 1);
        }else{
            cur += (xtop - x1 + 1) * (y2 - y1 + 1);
        }
        if((ri - li + 1) % 2 != 0){
            if(col) cur += 1LL * (y2 - y1 + 1) * sz;
            else cur -= 1LL * (y2 - y1 + 1) * sz;
        }
        ll xbottom = ri * sz;
        if(CC(ri, rj, c00)){
            cur -= (x2 - xbottom + 1) * (y2 - y1 + 1);
        }else{
            cur += (x2 - xbottom + 1) * (y2 - y1 + 1);
        }
        return cur;
    }
    if(x1 % sz != 0 || (x2 + 1) % sz != 0){
        int x1top = (li+1) * sz - 1;
        int x1bottom = ri * sz;
        return calc(sz, x1, x1top, y1, y2, c00) + calc(sz, x1top+1, x1bottom-1, y1, y2, c00) + calc(sz, x1bottom, x2, y1, y2, c00);
    }
    if(y1 % sz != 0 || (y2 + 1) % sz != 0){
        int yleft = (lj + 1) * sz - 1;
        int yright = rj * sz;
        return calc(sz, x1, x2, y1, yleft, c00) + calc(sz, x1, x2, yleft+1, yright-1, c00) + calc(sz, x1, x2, yright, y2, c00);
    }
    if((ri - li + 1) % 2 != 0 && (rj - lj + 1) % 2 != 0){
        if(col) cur -= 1LL * sz * sz;
        else cur += 1LL * sz * sz;
    }
    return cur;
}

void solve(int sz, int c00){
    ll cur = 0;
    f1(i,k){
        int x1 = a[i].x1, x2 = a[i].x2, y1 = a[i].y1, y2 = a[i].y2;
        cur += calc(sz, x1, x2, y1, y2, c00);
    }
    ll v = 1LL * (n / sz) * (n / sz);
    cur += (v / 2) * sz * sz;
    if(v % 2 == 1 && c00) cur += sz * sz;
//    cout << sz << ' ' << cur << endl;
    ans = min(ans, cur);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp", "r", stdin);
        freopen(__file_name ".out", "w", stdout);
    }
    // code here
    cin >> n >> k;
    f1(i,k){
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
        a[i].x1--; a[i].y1--; a[i].x2--; a[i].y2--;
    }
    ans = inf;
    for(int i = 1; i * i <= n; i++){
        if(n % i == 0){
            solve(i, 0);
            solve(i, 1);
            if(i * i != n && i != 1){
                solve(n / i, 0);
                solve(n / i, 1);
            }
        }
    }
    cout << ans;
    return 0;
}

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

chessboard.cpp: In function 'int main()':
chessboard.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(__file_name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
chessboard.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(__file_name ".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