oj.uz

Submission #779255

# Submission time Handle Problem Language Result Execution time Memory
779255 2023-07-11T09:34:05 Z vjudge1 Chessboard (IZhO18_chessboard) C++17
0 / 100
 285 ms 984 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 285 ms 984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 285 ms 984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -