Submission #891641

#	Time	Username	Problem	Language	Result	Execution time	Memory
891641		boris_mihov	Hamburg Steak (JOI20_hamburg)	C++17	2 / 100	3062 ms	35316 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 <Rectangle> solveFor;

void brute(int idx, std::vector <Rectangle> &sol)
{
    if (sol.size() > k)
    {
        return;
    }

    if (idx == n)
    {
        while (sol.size() < k)
        {
            sol.push_back(sol.back());
        }

        for (const Rectangle &curr : sol)
        {
            std::cout << curr.down.x << ' ' << curr.down.y << '\n';
        }

        exit(0);
    }

    std::vector <Rectangle> newSol;
    for (int i = 0 ; i < sol.size() ; ++i)
    {
        if (sol[i].intersectWith(solveFor[idx]))
        {
            newSol = sol;
            newSol[i] = sol[i].intersectionWith(solveFor[idx]);
            brute(idx + 1, newSol);
        }
    }

    newSol = sol;
    newSol.push_back(solveFor[idx]);
    brute(idx + 1, newSol);
}

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

    std::shuffle(solveFor.begin(), solveFor.end(), rng);
    std::vector <Rectangle> empty;
    brute(0, empty);
    assert(false);
}

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 'void brute(int, std::vector<Rectangle>&)':
hamburg.cpp:47:20: warning: comparison of integer expressions of different signedness: 'std::vector<Rectangle>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if (sol.size() > k)
      |         ~~~~~~~~~~~^~~
hamburg.cpp:54:27: warning: comparison of integer expressions of different signedness: 'std::vector<Rectangle>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         while (sol.size() < k)
      |                ~~~~~~~~~~~^~~
hamburg.cpp:68:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Rectangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0 ; i < sol.size() ; ++i)
      |                      ~~^~~~~~~~~~~~

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