제출 #1242993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242993		tvgk	산악 구조대 (JOI13_mountain)	C++20	100 / 100	13 ms	776 KiB

mountain

#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e2 + 2, MOD = 1e9 + 7;

int pre[mxN][mxN];
bool a[mxN][mxN];

void Rot(ii& l, ii& r, ii top, ii cor)
{
    l.fi = min(top.fi, cor.fi);
    l.se = min(top.se, cor.se);
    r.fi = max(top.fi, cor.fi);
    r.se = max(top.se, cor.se);
}

int Get(ii u, ii v)
{
    ii l, r;
    Rot(l, r, u, v);
    return pre[r.fi][r.se] - pre[l.fi - 1][r.se] - pre[r.fi][l.se - 1] + pre[l.fi - 1][l.se - 1];
}

void Erase(ii u, ii v)
{
    ii l, r;
    Rot(l, r, u, v);
    for (int i = l.fi; i <= r.fi; i++)
    {
        for (int j = l.se; j <= r.se; j++)
            a[i][j] = 0;
    }
}

void Binary(ii top, ii cor, int h)
{
    ii l, r;
    Rot(l, r, top, cor);

    for (int i = l.fi - 1; i <= r.fi; i++)
        pre[i][l.se - 1] = 0;
    for (int i = l.se - 1; i <= r.se; i++)
        pre[l.fi - 1][i] = 0;

    while (1)
    {
        for (int i = l.fi; i <= r.fi; i++)
        {
            for (int j = l.se; j <= r.se; j++)
                pre[i][j] = a[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        }

        if (!pre[r.fi][r.se])
            return;

        int mx = 0;
        ii vt = l;
        for (int i = l.fi; i <= r.fi; i++)
        {
            for (int j = l.se; j <= r.se; j++)
            {
                if (!a[i][j])
                    continue;

                int tmp = min(Get(top, {i, j}), Get(cor, {i, j}));
                if (mx < tmp)
                {
                    mx = tmp;
                    vt = {i, j};
                }
            }
        }

        int tmp = Measure(vt.fi, vt.se);
        if (tmp == h)
            Pinpoint(vt.fi, vt.se);

        if (tmp < h)
            Erase(vt, cor);
        else
            Erase(vt, top);
    }
}

void Rescue(int nRow, int nCol, int u, int v, int h)
{
    for (int i = 1; i <= nRow; i++)
    {
        for (int j = 1; j <= nCol; j++)
            a[i][j] = 1;
    }

    Binary({u, v}, {1, 1}, h);
    Binary({u, v}, {nRow, nCol}, h);
    Binary({u, v}, {1, nCol}, h);
    Binary({u, v}, {nRow, 1}, h);
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80