oj.uz

Submission #891640

# Submission time Handle Problem Language Result Execution time Memory
891640 2023-12-23T12:07:52 Z boris_mihov Hamburg Steak (JOI20_hamburg) C++17
2 / 100
 3000 ms 48064 KB 
#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);
    brute(0, {});
    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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 888 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 888 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 92 ms 47692 KB Output is correct
6 Correct 90 ms 47804 KB Output is correct
7 Correct 90 ms 48064 KB Output is correct
8 Correct 96 ms 47284 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -