Submission #747056

#	Time	Username	Problem	Language	Result	Execution time	Memory
747056		heeheeheehaaw	Chessboard (IZhO18_chessboard)	C++17	39 / 100	205 ms	12056 KiB

chessboard

#include <iostream>
#include <vector>

using namespace std;

int a[1005][1005];
int spw[1005][1005], spb[1005][1005];

int main()
{
    int n, k;
    cin>>n>>k;

    for(int i = 1; i <= k; i++)
    {
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;
        if(n <= 1000)
        a[x1][y1] = 1;
    }

    if(n > 1000)
    {
        int minn = n * n;
        for(int pas = 0; pas <= 1; pas++)
        {
            int col = pas, sum = 0;
            for(int i = 1; i <= n; i++)
            {
                if(i % 2 == 0)
                    col = pas;
                else
                    col = 1 - pas;
                for(int j = 1; j <= n; j++)
                {
                    if(col == 0)
                        sum += spb[i][j] - spb[i - 1][j] - spb[i][j - 1] + spb[i - 1][j - 1];
                    else
                        sum += spw[i][j] - spw[i - 1][j] - spw[i][j - 1] + spw[i - 1][j - 1];
                    col = 1 - col;
                }
            }

            minn = min(minn, sum);
        }

        cout<<minn<<'\n';
        return 0;
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            if(a[i][j] == 0) spw[i][j]++;
            else spb[i][j]++;
            spw[i][j] += spw[i][j - 1] + spw[i - 1][j] - spw[i - 1][j - 1];
            spb[i][j] += spb[i][j - 1] + spb[i - 1][j] - spb[i - 1][j - 1];
        }

    vector<int> divs;
    for(int i = 1; i * i <= n; i++)
        if(n % i == 0)
        {
            divs.push_back(i);
            if(i * i != n && i != 1)
                divs.push_back(n / i);
        }

    int minn = n * n;
    for(auto d : divs)
    {
        for(int pas = 0; pas <= 1; pas++)
        {
            int col = pas, sum = 0;
            for(int i = d; i <= n; i += d)
            {
                if((i / d) % 2 == 0)
                    col = pas;
                else
                    col = 1 - pas;
                for(int j = d; j <= n; j += d)
                {
                    if(col == 0)
                        sum += spb[i][j] - spb[i - d][j] - spb[i][j - d] + spb[i - d][j - d];
                    else
                        sum += spw[i][j] - spw[i - d][j] - spw[i][j - d] + spw[i - d][j - d];
                    col = 1 - col;
                }
            }

            minn = min(minn, sum);
        }
    }

    cout<<minn<<'\n';

    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