Submission #891636

#	Time	Username	Problem	Language	Result	Execution time	Memory
891636		boris_mihov	Hamburg Steak (JOI20_hamburg)	C++17	1 / 100	1117 ms	1048576 KiB

hamburg

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <chrono>
#include <stack>
#include <queue>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

struct Point
{
    int x, y;
};

struct Rectangle
{
    Point down, up;
    bool intersectWith(Rectangle b)
    {
        if (std::max(down.x, b.down.x) > std::min(up.x, b.up.x)) return false;
        if (std::max(down.y, b.down.y) > std::min(up.y, b.up.y)) return false;
        return true;
    }

    Rectangle intersectionWith(Rectangle b)
    {
        Rectangle result;
        result.down.x = std::max(down.x, b.down.x);
        result.down.y = std::max(down.y, b.down.y);
        result.up.x = std::min(up.x, b.up.x);
        result.up.y = std::min(up.y, b.up.y);
        return result;
    }
};

int n, k;
Rectangle rects[MAXN];
std::vector <Point> solution;

std::vector <Rectangle> rec(std::vector <Rectangle> &curr)
{
    if (curr.size() == 1)
    {
        return curr;
    }

    std::vector <std::vector <Rectangle>> split;
    for (const Rectangle &currRect : curr)
    {
        bool found = false;
        for (int i = 0 ; i < split.size() ; ++i)
        {
            if (split[i][0].intersectWith(currRect))
            {
                found = true;
                split[i].push_back(currRect);
            }
        }

        if (!found)
        {
            split.push_back({currRect});
            continue;
        }
    }

    if (split.size() == 1)
    {
        Rectangle begin = split[0][0];
        split[0].erase(split[0].begin());
        std::vector <Rectangle> sol = rec(split[0]);

        for (int i = 0 ; i < sol.size() ; ++i)
        {
            assert(sol[i].intersectWith(begin));
            sol[i] = sol[i].intersectionWith(begin);
        }

        return sol;
    }

    std::vector <Rectangle> sol;
    for (std::vector <Rectangle> &currSplit : split)
    {
        std::vector <Rectangle> res = rec(currSplit);
        for (const Rectangle &r : res)
        {
            sol.push_back(r);
        }
    }

    return sol;
}

std::mt19937 rng(69420); //std::chrono::steady_clock::now().time_since_epoch().count());
void solve()
{
    std::vector <Rectangle> solveFor;
    for (int i = 1 ; i <= n ; ++i)
    {
        solveFor.push_back(rects[i]);
    }

    std::shuffle(solveFor.begin(), solveFor.end(), rng);
    std::vector <Rectangle> mySol = rec(solveFor);

    for (int i = 0 ; i < mySol.size() ; ++i)
    {
        solution.push_back(mySol[i].down);
    }

    assert(1 <= solution.size() && solution.size() <= k);
    while (solution.size() < k) solution.push_back(solution.back());

    for (const Point &curr : solution)
    {
        std::cout << curr.x << ' ' << curr.y << '\n';
    }
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> rects[i].down.x >> rects[i].down.y >> rects[i].up.x >> rects[i].up.y;
        if (rects[i].down.x > rects[i].up.x) std::swap(rects[i].down.x, rects[i].up.x);
        if (rects[i].down.y > rects[i].up.y) std::swap(rects[i].down.y, rects[i].up.y);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    
    return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'std::vector<Rectangle> rec(std::vector<Rectangle>&)':
hamburg.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<Rectangle> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0 ; i < split.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
hamburg.cpp:78:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Rectangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int i = 0 ; i < sol.size() ; ++i)
      |                          ~~^~~~~~~~~~~~
hamburg.cpp: In function 'void solve()':
hamburg.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Rectangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (int i = 0 ; i < mySol.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from hamburg.cpp:4:
hamburg.cpp:117:52: warning: comparison of integer expressions of different signedness: 'std::vector<Point>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |     assert(1 <= solution.size() && solution.size() <= k);
      |                                    ~~~~~~~~~~~~~~~~^~~~
hamburg.cpp:118:28: warning: comparison of integer expressions of different signedness: 'std::vector<Point>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |     while (solution.size() < k) solution.push_back(solution.back());
      |            ~~~~~~~~~~~~~~~~^~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 0 / 1
• Subtask 6: 0 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79