Submission #368088

#	Time	Username	Problem	Language	Result	Execution time	Memory
368088		nicolaalexandra	Chessboard (IZhO18_chessboard)	C++14	100 / 100	879 ms	6548 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

long long n,k,i,x,y,x2,y2;
struct dreptunghi{
    long long x,y,x2,y2;
};
vector <dreptunghi> v;

long long count_(long long x, long long y, long long val){
    if (!x || !y)
        return 0;

    long long sol = 1LL * (x/val) * (y/val) / 2 * val * val;
    long long lastx = (x/val) * val, lasty = (y/val) * val;

    if (x/val % 2)
        sol +=  (y/val + 1)/2  * val * (x - lastx);
    else sol += (y/val/2) * val * (x - lastx);


    if (y/val % 2)
        sol += (x/val + 1)/2 * val * (y - lasty);
    else sol += (x/val/2) * val * (y - lasty);


    if (!(x/val % 2 == y/val%2))
        sol += (x - lastx) * (y - lasty);

    return sol;
}

long long solve (long long val){
    long long albe = 1LL * (n/val) * (n/val) / 2 * val * val; /// cate ar trebui sa fac albe daca e toata tabla neagra
    long long negre = 1LL * n * n - albe;

    for (auto it : v){
        long long x = it.x, y = it.y, x2 = it.x2, y2 = it.y2;

        long long cnt = count_(x2,y2,val) - count_(x2,y-1,val) - count_(x-1,y2,val) + count_(x-1,y-1,val);

        negre -= (x2-x+1) * (y2-y+1) - cnt; /// nu are sens sa le fac pe astea negre
        negre += cnt; /// trb sa le fac la loc  albe pe astea

        albe += (x2-x+1) * (y2-y+1) - cnt;
        albe -= cnt;
    }

    return min (albe,negre);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k;
    for (i=1;i<=k;i++){
        cin>>x>>y>>x2>>y2;
        v.push_back({x,y,x2,y2});
    }

    long long sol = 1LL * n * n;
    for (long long d=1;d<n;d++){
        if (n % d == 0)
            sol = min (sol,solve(d));
    }

    cout<<sol;

    return 0;
}

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