Submission #779255

#	Time	Username	Problem	Language	Result	Execution time	Memory
779255		vjudge1	Chessboard (IZhO18_chessboard)	C++17	0 / 100	285 ms	984 KiB

chessboard

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

long long n, k;
long long ans = LLONG_MAX;
struct square
{
    int x, y;
};
vector <square> squares;

void solve(int squareSize)
{
    long long idk = (n / squareSize), idk2;
//    cout << squareSize << "\n";
    if(idk % 2)
        idk2 = idk * (idk / 2) + (idk + 1) / 2;
    else
        idk2 = idk * idk / 2;
//    cout << idk << "\n";
    long long cnt1 = 1ll * squareSize * squareSize * idk2, cnt2 = 1ll * n * n - cnt1;
//    cout << cnt1 << " " << cnt2 << "\n";
    for(auto x : squares)
    {
        long long r1, c1, r2, c2, a, b;
        c1 = x.x / squareSize;
        r1 = x.x % squareSize;

        if(r1)
            c1 ++;
        a = c1 % 2;

        c2 = x.y / squareSize;
        r2 = x.y % squareSize;

        if(r2)
            c2 ++;
        b = c2 % 2;

        /// incepem cu alb
        if(a == 1  &&  b == 0)
        {
//            cout << x.x << " " << x.y << "patrat negru\n";
            cnt2 --;
        }
        else if(a == 1  &&  b == 1)
        {
//            cout << x.x << " " << x.y << "patrat alb\n";
            // patrat alb
            cnt2 ++;

        }
        else if(a == 0  &&  b == 0)
        {
//            cout << x.x << " " << x.y << "patrat alb\n";
            // patrat alb
            cnt2 ++;
        }
        else
        {
//            cout << x.x << " " << x.y << "patrat negru\n";
            // patrat negru
            cnt2 --;
        }

        /// acum negru
        if(a == 1  &&  b == 0)
        {
//            cout << x.x << " " << x.y << "patrat alb\n";
            // patrat alb
            cnt1 ++;
        }
        else if(a == 1  &&  b == 1)
        {
//            cout << x.x << " " << x.y << "patrat negru\n";
            // patrat negru
            cnt1 --;
        }
        else if(a == 0  &&  b == 0)
        {
//            cout << x.x << " " << x.y << "patrat negru\n";
            // patrat negru
            cnt1 --;
        }
        else
        {
//            cout << x.x << " " << x.y << "patrat alb\n";
            // patrat alb
            cnt1 ++;
        }
    }
    ans = min(ans, min(cnt1, cnt2));
//    cout << cnt1 << " " << cnt2 << "\n\n";
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);

    cin >> n >> k;
    for(int i = 1; i <= k; i ++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        squares.pb({x1, y1});
    }

    long long d = 1;
    while(d * d <= n)
    {
        if(n % d == 0)
            solve(d);
        if(d != 1  &&  d * d != n)
            solve(n / d);
        d ++;
    }

    cout << ans;
    return 0;
}

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