Submission #779381

#	Time	Username	Problem	Language	Result	Execution time	Memory
779381		vjudge1	Chessboard (IZhO18_chessboard)	C++17	39 / 100	114 ms	5840 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 main()
{
    speedy();
    int n, k;
    cin >> n >> k;
    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