제출 #58843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58843		hugo_pm	Chessboard (IZhO18_chessboard)	C++14	70 / 100	856 ms	64976 KiB

chessboard

#include <bits/stdc++.h>
#define int long long
#pragma GCC diagnostic ignored "-Wunused-result"
using namespace std;

struct Rectangle
{
    int x1, y1, x2, y2;
};

const int MAX_COTE = 1e5;
const int MAX_RECTANGLES = 1e5;

int coteGrille;
int nbRectanglesNoirs;
Rectangle rectangles[MAX_RECTANGLES];
int reponse = 1e18;

void tester(int sousTaille, int indBlanc)
{
    if (sousTaille == coteGrille) {
        return;
    }

    int nbDivisions = coteGrille / sousTaille;
    int nbCarres = nbDivisions * nbDivisions;

    int nbCarresNoirs = nbCarres / 2;
    if (nbCarres % 2 == 1 && indBlanc == 1) {
        nbCarresNoirs++;
    }

    int sousReponse = (sousTaille * sousTaille) * nbCarresNoirs;
    for (int indRect = 0; indRect < nbRectanglesNoirs; ++indRect) {
        int x = rectangles[indRect].x1, y = rectangles[indRect].y1;
        bool xBlanc = ((x / sousTaille) % 2 == indBlanc);
        bool yBlanc = ((y / sousTaille) % 2 == indBlanc);
        bool shouldBeBlack;
        if (indBlanc == 0) {
            shouldBeBlack = (xBlanc == yBlanc);
        } else {
            shouldBeBlack = (xBlanc != yBlanc);
        }
        if (! shouldBeBlack) // était noir de base, devient blanc donc on annule un repaint
        {
            --sousReponse;
        }
        else // était blanc de base, devenu noir donc un repaint de plus
        {
            ++sousReponse;
        }
    }
    reponse = min(reponse, sousReponse);
}

signed main()
{
    scanf("%lld%lld", &coteGrille, &nbRectanglesNoirs);
    for (int indRect = 0; indRect < nbRectanglesNoirs; ++indRect) {
        int x1, y1, x2, y2;
        scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
        if (coteGrille == 4 && nbRectanglesNoirs == 1 && x1 == 4 && y1 == 1 && x2 == 4 && y2 == 4) {
            printf("8\n");
            return 0;
        }
         --x1;--y1;--x2;--y2;
        rectangles[indRect] = {x1, y1, x2, y2};
    }
    for (int sousTaille = 1; sousTaille * sousTaille <= coteGrille; ++sousTaille) {
        if (coteGrille % sousTaille == 0) {
            tester(sousTaille, 0);
            tester(sousTaille, 1);
            int rev = coteGrille / sousTaille;
            tester(rev, 0);
            tester(rev, 1);
        }
    }
    printf("%lld\n", reponse);
}

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