제출 #378591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378591		balbit	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1502 ms	11116 KiB

chessboard

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;

#define ll long long
#define int ll
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define pii pair<int, int>
#define SZ(x) (int)((x).size())
#define ALL(x) x.begin(), x.end()
#define pb push_back
#define MX(a,b) a = max(a,b)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

struct rect{
    int x,y,d;
};

int ps[2][100005];

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);
    int n,k; cin>>n>>k;
    vector<rect> v; v.reserve(k*4);
    ll rr = 0;
    REP(i,k) {
        ll r1,c1,r2,c2; cin>>r1>>c1>>r2>>c2;
        rr += (r2-r1+1) * (c2-c1+1);
        --r1; --c1;
        v.pb({r2,c2,1});
        v.pb({r1,c1,1});
        v.pb({r2,c1,-1});
        v.pb({r1,c2,-1});
    }
    ll re = 1e18;
    for (int d = 1; d<n; ++d) {
        if (n % d == 0) {
            ll totb = (n*n + ((n/d)&1?d*d:0))/2;
            REP1(i,n) {
                if (i) ps[0][i] = ps[0][i-1];
                ps[0][i] += ((i-1)/d)%2==0;
                ps[1][i] = i-ps[0][i];
            }
            bug(d, totb);
            int over = 0;
            for (rect r : v) {
                if (r.x>=0&&r.y>=0) {
                    int tmp = 0;
                    int rx = r.x/d, ry = r.y/d;
                    tmp += (r.x-rx*d) * (ps[((r.x-1)/d)&1][r.y]);
//                    r.x -= r.x%d;
                    tmp += (r.y%d) * (ps[((r.y-1)/d)&1][rx*d]);
//                    r.y -= r.y%d;
//                    --r.x; --r.y;
                    if (((rx)&1) && ((ry)&1)) {
                        tmp += ((rx*ry+1)*d*d)/2;
                    }else{
                        tmp += rx*ry*d*d/2;
                    }
                    over += tmp * r.d;
                }
            }
            bug(over);
            bug(totb + rr - over*2);
//            MX(over, rr-over);
            re = min(re, totb + rr - over*2);
            over = rr-over;
            re = min(re, n*n-totb + rr - over*2);
        }
    }
    cout<<re<<endl;
}

/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/

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