Submission #779426

#	Time	Username	Problem	Language	Result	Execution time	Memory
779426		vjudge1	Chessboard (IZhO18_chessboard)	C++17	39 / 100	126 ms	4596 KiB

chessboard

#include <iostream>
#define MAX 1000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
int a[MAX + 10][MAX + 10];
void speedy()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
int prime(int x)
{
    for (int d = 2; d * d <= x; d++)
        if (x % d == 0)
            return 0;
    return 1;
}
int main()
{
    speedy();
    int n, k;
    cin >> n >> k;
    if (prime(n) == 1)
    {
        long long change1 = n * n / 2, change2 = n * n / 2 + 1;
        for (int kk = 1; kk <= k; kk++)
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            ///make (1, 1) white
            if (x1 % 2 == 1 && y1 % 2 == 1)
            {
                change1++;
                change2--;
            }
            if (x1 % 2 == 0 && y1 % 2 == 0)
            {
                change1++;
                change2--;
            }
            ///make (1, 1) black
            if (x1 % 2 == 1 && y1 % 2 == 0)
            {
                change2++;
                change1--;
            }
            if (x1 % 2 == 0 && y1 % 2 == 1)
            {
                change2++;
                change1--;
            }
        }
        cout << min(change1, change2);
    }
    else
    {
        for (int kk = 1; kk <= k; kk++)
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            for (int i = x1; i <= x2; i++)
                for (int j = y1; j <= y2; j++)
                    a[i][j] = 1;
        }
        int ans = n * n + 10;
        for (int side = 1; side < n; side++)
            if (n % side == 0)
            {
                int change, cnt = n / side;
                ///make (1, 1, side, side) white
                change = 0;
                for (int auxi = 1; auxi <= cnt; auxi++)
                    for (int auxj = 1; auxj <= cnt; auxj++)
                        for (int i = side * (auxi - 1) + 1; i <= side * auxi; i++)
                            for (int j = side * (auxj - 1) + 1; j <= side * auxj; j++)
                            {
                                if (auxi % 2 == 1 && auxj % 2 == 1)
                                    if (a[i][j] == 1)
                                        change++;
                                if (auxi % 2 == 1 && auxj % 2 == 0)
                                    if (a[i][j] == 0)
                                        change++;
                                if (auxi % 2 == 0 && auxj % 2 == 1)
                                    if (a[i][j] == 0)
                                        change++;
                                if (auxi % 2 == 0 && auxj % 2 == 0)
                                    if (a[i][j] == 1)
                                        change++;
                            }
                ans = min(ans, change);
                ///make (1, 1, side, side) black
                change = 0;
                for (int auxi = 1; auxi <= cnt; auxi++)
                    for (int auxj = 1; auxj <= cnt; auxj++)
                        for (int i = side * (auxi - 1) + 1; i <= side * auxi; i++)
                            for (int j = side * (auxj - 1) + 1; j <= side * auxj; j++)
                            {
                                if (auxi % 2 == 1 && auxj % 2 == 1)
                                    if (a[i][j] == 0)
                                        change++;
                                if (auxi % 2 == 1 && auxj % 2 == 0)
                                    if (a[i][j] == 1)
                                        change++;
                                if (auxi % 2 == 0 && auxj % 2 == 1)
                                    if (a[i][j] == 1)
                                        change++;
                                if (auxi % 2 == 0 && auxj % 2 == 0)
                                    if (a[i][j] == 0)
                                        change++;
                            }
                ans = min(ans, change);
            }
        cout << ans;
    }
    return 0;
}

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