Submission #93171

#	Time	Username	Problem	Language	Result	Execution time	Memory
93171		SamAnd	Chessboard (IZhO18_chessboard)	C++17	100 / 100	1996 ms	4344 KiB

chessboard

#include <iostream>
#include <cstdio>
using namespace std;
#define m_p make_pair
const int N = 100005;
struct ban
{
    int x, y;
    ban(){}
    ban(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};

int n;

int m;
pair<ban, ban> a[N];

bool vv;
bool sevv(int x, int y, int t)
{
    x = x / t;
    y = y / t;
    if ((x + y) % 2 == 0)
    {
        if (vv)
            return true;
        else
            return false;
    }
    else
    {
        if (vv)
            return false;
        else
            return true;
    }
}

long long sev(const pair<ban, ban>& a, int t)
{
    int x1 = a.first.x;
    int y1 = a.first.y;
    int x2 = a.second.x;
    int y2 = a.second.y;

    int xm1 = (x1 / t + 1) * t;
    if (x1 % t == 0)
        xm1 = x1;
    int xm2 = (x2 / t) * t - 1;
    if (x2 % t == t - 1)
        xm2 = x2;
    int ym1 = (y1 / t + 1) * t;
    if (y1 % t == 0)
        ym1 = y1;
    int ym2 = (y2 / t) * t - 1;
    if (y2 % t == t - 1)
        ym2 = y2;

    long long ans = 0;

    // y1; ym1 - 1
    // x1; xm1 - 1
    long long xx = 0;
    if (sevv(x1, y1, t))
        xx += (xm1 - x1);
    // xm1; xm2
    if (!sevv(xm1, y1, t))
        xx += ((((xm2 - xm1 + 1) / t) / 2) * t);
    else
        xx += ((((xm2 - xm1 + 1) / t) - (((xm2 - xm1 + 1) / t) / 2)) * t);
    // xm2 + 1; x2
    if (sevv(xm2 + 1, y1, t))
        xx += (x2 - xm2);
    if (xm1 - xm2 == t + 1)
    {
        xx = 0;
        if (sevv(x1, y1, t))
            xx = (x2 - x1 + 1);
    }
    ans += ((ym1 - y1) * xx);

    // ym1; ym2
    // x1; xm1 - 1
    xx = 0;
    if (sevv(x1, ym1, t))
        xx += (xm1 - x1);
    // xm1; xm2
    if (!sevv(xm1, ym1, t))
        xx += ((((xm2 - xm1 + 1) / t) / 2) * t);
    else
        xx += ((((xm2 - xm1 + 1) / t) - (((xm2 - xm1 + 1) / t) / 2)) * t);
    // xm2 + 1; x2
    if (sevv(xm2 + 1, ym1, t))
        xx += (x2 - xm2);
    if (xm1 - xm2 == t + 1)
    {
        xx = 0;
        if (sevv(x1, ym1, t))
            xx = (x2 - x1 + 1);
    }
    ans += ((((ym2 - ym1 + 1) / t) / 2) * ((x2 - x1 + 1) - xx) * t);
    ans += ((((ym2 - ym1 + 1) / t) - (((ym2 - ym1 + 1) / t) / 2)) * xx * t);

    // ym2 + 1; y2
    // x1; xm1 - 1
    xx = 0;
    if (sevv(x1, ym2 + 1, t))
        xx += (xm1 - x1);
    // xm1; xm2
    if (!sevv(xm1, ym2 + 1, t))
        xx += ((((xm2 - xm1 + 1) / t) / 2) * t);
    else
        xx += ((((xm2 - xm1 + 1) / t) - (((xm2 - xm1 + 1) / t) / 2)) * t);
    // xm2 + 1; x2
    if (sevv(xm2 + 1, ym2 + 1, t))
        xx += (x2 - xm2);
    if (xm1 - xm2 == t + 1)
    {
        xx = 0;
        if (sevv(x1, ym2 + 1, t))
            xx = (x2 - x1 + 1);
    }
    ans += ((y2 - ym2) * xx);

    if (ym1 - ym2 == t + 1)
    {
        ans = 0;
        xx = 0;
        if (sevv(x1, y1, t))
            xx += (xm1 - x1);
        // xm1; xm2
        if (!sevv(xm1, y1, t))
            xx += ((((xm2 - xm1 + 1) / t) / 2) * t);
        else
            xx += ((((xm2 - xm1 + 1) / t) - (((xm2 - xm1 + 1) / t) / 2)) * t);
        // xm2 + 1; x2
        if (sevv(xm2 + 1, y1, t))
            xx += (x2 - xm2);
        if (xm1 - xm2 == t + 1)
        {
            xx = 0;
            if (sevv(x1, y1, t))
                xx = (x2 - x1 + 1);
        }
        ans += (xx * (y2 - y1 + 1));
    }

    return ans;
}

long long spi(const pair<ban, ban>& a, int t)
{
    int x1 = a.first.x;
    int y1 = a.first.y;
    int x2 = a.second.x;
    int y2 = a.second.y;
    return 1LL * (x2 - x1 + 1) * (y2 - y1 + 1) - sev(a, t);
}

long long ans;
void stg(int t)
{
    vv = true;
    long long yans = 0;
    long long g = 0;
    for (int i = 0; i < m; ++i)
    {
        long long spii = spi(a[i], t);
        yans += (spii);
        g += (1LL * (a[i].second.x - a[i].first.x + 1) * (a[i].second.y - a[i].first.y + 1) - spii);
    }
    yans += (sev(m_p(ban(0, 0), ban(n - 1, n - 1)), t) - g);
    ans = min(ans, yans);
    vv = false;
    yans = 0;
    g = 0;
    for (int i = 0; i < m; ++i)
    {
        long long spii = spi(a[i], t);
        yans += (spii);
        g += (1LL * (a[i].second.x - a[i].first.x + 1) * (a[i].second.y - a[i].first.y + 1) - spii);
    }
    yans += (sev(m_p(ban(0, 0), ban(n - 1, n - 1)), t) - g);
    ans = min(ans, yans);
}

int b[8][8];
int main()
{
    /*vv = true;
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            if (sevv(i, j, 1))
                b[i][j] = 1;
        }
    }
    for (int x1 = 0; x1 < 6; ++x1)
    {
        for (int x2 = x1; x2 < 6; ++x2)
        {
            for (int y1 = 0; y1 < 6; ++y1)
            {
                for (int y2 = y1; y2 < 6; ++y2)
                {
                    cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << endl;
                    if (x1 == 4 && x2 == 4 && y1 == 0 && y2 == 4)
                        cout << "";
                    int ans1 = sev(m_p(ban(x1, y1), ban(x2, y2)), 1);
                    int ans2 = 0;
                    for (int i = x1; i <= x2; ++i)
                    {
                        for (int j = y1; j <= y2; ++j)
                        {
                            ans2 += b[i][j];
                        }
                    }
                    if (ans1 != ans2)
                        cout << "asdfdafjklshdfkjhaskjldfhakjl" << endl;
                }
            }
        }
    }*/
    //freopen("input2.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d%d", &a[i].first.x, &a[i].first.y, &a[i].second.x, &a[i].second.y);
        --a[i].first.x;
        --a[i].first.y;
        --a[i].second.x;
        --a[i].second.y;
    }
    ans = 1LL * n * n;
    for (int i = 1; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            if (i != n)
                stg(i);
            if (n / i != n)
                stg(n / i);
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:230:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
chessboard.cpp:233:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &a[i].first.x, &a[i].first.y, &a[i].second.x, &a[i].second.y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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