제출 #93140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93140		SamAnd	Chessboard (IZhO18_chessboard)	C++14	70 / 100	1266 ms	1916 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;
    if (x1 == x2 && y1 == y2)
        return sevv(x1, y1, t);
    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;
    long long xx = 0;

    if (xm1 - xm2 == t + 1)
    {
        if (sevv(x1, y1, t))
            xx = (x2 - x1 + 1);
        goto kovx;
    }
    // x1; xm1 - 1
    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);

    kovx:

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

    kovy:

    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)
    {
        yans += (spi(a[i], t));
        g += (sev(a[i], t));
    }
    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)
    {
        yans += (spi(a[i], t));
        g += (sev(a[i], t));
    }
    yans += (sev(m_p(ban(0, 0), ban(n - 1, n - 1)), t) - g);
    ans = min(ans, yans);
}

int main()
{
    //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;
}

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp: In function 'int main()':
chessboard.cpp:146: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:149: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: 0 / 30