Submission #1211676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211676		dima2101	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	2513 ms	182492 KiB

joioi

#include <bits/stdc++.h>

struct Node
{
    int i, j, num;
    Node(int i, int j, int num) : i(i), j(j), num(num) {};
    Node() = default;
};

bool Check1(std::vector<Node> &first, std::vector<Node> &second, int h, int w)
{
    std::vector<int> first_max(h, -1);
    std::vector<int> second_min(h, 1e9);
    for (int i = 0; i < first.size(); i++)
    {
        first_max[first[i].i] = std::max(first[i].j, first_max[first[i].i]);
    }
    for (int i = 0; i < second.size(); i++)
    {
        second_min[second[i].i] = std::min(second[i].j, second_min[second[i].i]);
    }
    int prev = -1;
    bool was = true;
    for (int i = 0; i < h; i++)
    {
        int cur = std::max(prev, first_max[i]);
        if (cur >= second_min[i])
        {
            was = false;
        }
        prev = cur;
    }
    if (was)
    {
        return true;
    }

    prev = -1;
    for (int i = h - 1; i >= 0; i--)
    {
        int cur = std::max(prev, first_max[i]);
        if (cur >= second_min[i])
        {
            return false;
        }
        prev = cur;
    }
    return true;
}

bool Check3(std::vector<Node> &first, std::vector<Node> &second, int h, int w)
{
    std::vector<int> first_max(h, 1e9);
    std::vector<int> second_min(h, -1);
    for (int i = 0; i < first.size(); i++)
    {
        first_max[first[i].i] = std::min(first[i].j, first_max[first[i].i]);
    }
    for (int i = 0; i < second.size(); i++)
    {
        second_min[second[i].i] = std::max(second[i].j, second_min[second[i].i]);
    }
    int prev = w;
    bool was = true;
    for (int i = 0; i < h; i++)
    {
        int cur = std::min(prev, first_max[i]);
        if (second_min[i] >= cur)
        {
            was = false;
        }
        prev = cur;
    }
    if (was)
    {
        return true;
    }

    prev = w;
    for (int i = h - 1; i >= 0; i--)
    {
        int cur = std::min(prev, first_max[i]);
        if (second_min[i] >= cur)
        {
            return false;
        }
        prev = cur;
    }
    return true;
}

bool Check(std::vector<Node> &first, std::vector<Node> &second, int h, int w)
{
    return (Check1(first, second, h, w) ||
            Check3(first, second, h, w));
}

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int h, w;
    std::cin >> h >> w;

    std::vector<std::vector<int>> a(h, std::vector<int>(w));
    std::vector<Node> all;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            std::cin >> a[i][j];
            all.push_back(Node(i, j, a[i][j]));
        }
    }
    std::sort(all.begin(), all.end(), [&](Node a, Node b)
              { return a.num < b.num; });
    int l = -1,
        r = 1e9;
    while (l + 1 < r)
    {
        int mid = (l + r) / 2;

        std::vector<Node> first, second;
        for (int i = 0; i < all.size(); i++)
        {
            if (all[i].num - all[0].num > mid)
            {
                second.push_back(all[i]);
            }
            if (all.back().num - all[i].num > mid)
            {
                first.push_back(all[i]);
            }
        }
        // if (mid == 18)
        // {
        //     for (auto i : first)
        //     {
        //         std::cout << i.i << ' ' << i.j << ' ' << i.num << std::endl;
        //     }
        //     std::cout << std::endl;
        //     for (auto i : second)
        //     {
        //         std::cout << i.i << ' ' << i.j << ' ' << i.num << std::endl;
        //     }
        // }
        if (Check(first, second, h, w))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    std::cout << r;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40