Submission #1128980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128980		dwuy	Chessboard (IZhO18_chessboard)	C++20	100 / 100	456 ms	4248 KiB

chessboard

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "IZhO18_chessboard"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

struct Rect{
    int x, y, u, v;
    void read(){
        cin >> x >> y >> u >> v;
    }
};

int n, k;
Rect a[MX];

namespace SUB134{
    bool OK(){
        return n <= 1000;
    }

    const int MS = 1005;
    int r[MS][MS];

    void solve(){
        for(int i=1; i<=k; i++){
            for(int x=a[i].x; x<=a[i].u; x++){
                for(int y=a[i].y; y<=a[i].v; y++){
                    r[x][y] = 1;
                }
            }
        }
        int ans = 1e18;
        for(int d=1; d<n; d++) if(n%d == 0){
            int res = 0;
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    int w = ((i - 1)/d + (j - 1)/d)%2;
                    if(w) res += !r[i][j];
                    else res += r[i][j];
                }
            }
            ans = min({ans, res, n*n - res});
        }
        cout << ans;
    }
}

namespace SUB2{
    bool OK(){
        for(int i=2; i*i<=n; i++) if(n%i == 0) return 0;
        for(int i=1; i<=k; i++) if(a[i].x != a[i].u || a[i].y != a[i].v) return 0;
        return 1;
    }

    void solve(){
        int res = n*(n/2) + n/2;
        if(n == 2) res = 2;
        for(int i=1; i<=k; i++){
            int d = (a[i].x + a[i].y)%2;
            if(d) res--;
            else res++;
        }
        cout << min(res, n*n - res);
    }
}

namespace FULL{
    bool OK(){
        return 1;
    }

    int w[MX];

    int cnt(int x, int y, int u, int v, int mid){
        int height = u - x + 1;
        int width = v - y + 1;
        int ans = height/(2 * mid) * mid * width;
        height %= 2 * mid;

        int layer1 = 0;
        if((x - 1)/mid%2 == 0) layer1 = w[v] - w[y - 1];
        else layer1 = (v - y + 1) - (w[v] - w[y - 1]);
        int layer2 = width - layer1;
//        cout << height << ' ' << layer1 << ' ' << layer2 << endl;
        int thick = mid - (x - 1)%mid;
        ans += min(thick, height) * layer1;
        if(height > thick) ans += min(mid, height - thick) * layer2;
        if(height > thick + mid) ans += layer1*(height - thick - mid);
        return ans;
    }

    void solve(){
        int ans = 1e18;
        for(int u=1; u<n; u++) if(n%u == 0){
            int d = n/u;
            int cur = u*n*(d/2);
            if(d&1) cur += u*u*(d/2);

            for(int i=1; i<=n; i++){
                w[i] = w[i-1];
                if(((i - 1)/u)%2) w[i]++;
            }
//            cout << u << endl;
            for(int i=1; i<=k; i++){
                int delta = cnt(a[i].x, a[i].y, a[i].u, a[i].v, u);
//                cout << delta << endl;
                cur -= delta;
                cur += (a[i].u - a[i].x + 1)*(a[i].v - a[i].y + 1) - delta;
            }
//            cout << cur << " == " << n*n - cur << endl << endl;
            ans = min({ans, cur, n*n - cur});
        }
        cout << ans;
    }
}


int32_t main(){
    fastIO;
    //file(TASK);

    cin >> n >> k;
    for(int i=1; i<=k; i++) a[i].read();

//    if(SUB134::OK()) return SUB134::solve(), 0;
//    if(SUB2::OK()) return SUB2::solve(), 0;
    if(FULL::OK()) return FULL::solve(), 0;

//    int mx = 0;
//    for(int i=1; i<=1000; i++){
//        int ans = 0;
//        for(int j=1; j*j<=i; j++) if(i%j == 0){
//            ans++;
//            ans += j*j != i;
//        }
//        mx = max(mx, ans);
//    }
//    cerr << mx;

    return 0;
}
/**

max numbers of divisors : 128

-------test 0--------
2 0

$

2

-------test 1--------
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

$

14

-------test 2--------
4 1
4 1 4 4

$

8

**/

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