Submission #1211462

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

joioi

#include <bits/stdc++.h>
#define int long long

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

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;

        int left = -1;
        int right = 1e9;
        for (int i = 0; i < all.size(); i++)
        {
            if (all[i].num - all[0].num <= mid)
            {
                left = i;
            }
            if (all.back().num - all[i].num <= mid)
            {
                right = std::min(right, i);
            }
        }
        left++;
        right--;
        if (left <= right)
        {
            l = mid;
            continue;
        }
        std::vector<std::vector<char>> help(h, std::vector<char>(w, '#'));
        for (int i = 0; i <= right; i++)
        {
            help[all[i].i][all[i].j] = 'I';
        }
        for (int i = left; i < all.size(); i++)
        {
            help[all[i].i][all[i].j] = 'J';
        }
        bool can = true;
        for (int i = 0; i < h; i++)
        {
            std::string now;
            char prev = '#';
            for (int j = 0; j < w; j++)
            {
                if (help[i][j] == '#')
                {
                    continue;
                }
                if (prev != help[i][j])
                {
                    now += help[i][j];
                    prev = help[i][j];
                }
            }
            if (now.size() > 2)
            {
                can = false;
            }
        }
        for (int j = 0; j < w; j++)
        {
            std::string now;
            char prev = '#';
            for (int i = 0; i < h; i++)
            {
                if (help[i][j] == '#')
                {
                    continue;
                }
                if (prev != help[i][j])
                {
                    now += help[i][j];
                    prev = help[i][j];
                }
            }
            if (now.size() > 2)
            {
                can = false;
            }
        }
        if (can)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    std::cout << r;
}

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