Submission #747059

#	Time	Username	Problem	Language	Result	Execution time	Memory
747059		heeheeheehaaw	Chessboard (IZhO18_chessboard)	C++17	47 / 100	111 ms	23828 KiB

chessboard

#include <iostream>
#include <vector>
#define int long long

using namespace std;

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

signed main()
{
    int s1 = 0, s2 = 0;
    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;
        else
        {
            if((x1 + y1) % 2 == 0)
                s1++;
            else
                s2++;
        }
    }

    if(n > 1000)
    {
        int d1 = n * n / 2, d2 = n * n / 2;
        if(n % 2 == 1)
            d1++;
        int ans = min(d1 - s1 + s2, d2 - s2 + s1);
        cout<<ans<<'\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: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 0 / 23
• Subtask 6: 0 / 30