oj.uz

Submission #896948

# Submission time Handle Problem Language Result Execution time Memory
896948 2024-01-02T11:24:36 Z danikoynov Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 754 ms 82628 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;
struct event
{
    int tim, type, idx;

    event(int _tim = 0, int _type = 0, int _idx = 0)
    {
        tim = _tim;
        type = _type;
        idx = _idx;
    }

    bool operator < (const event &e) const
    {
        if (tim != e.tim)
            return tim < e.tim;
        return type > e.type;
    }

};
    unordered_map < int, int > mx, revx;
    unordered_map < int, int > my, revy;
struct point
{
    int x, y;

    point(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }

    void input()
    {
        cin >> x >> y;
    }

    void print()
    {
        cout << revx[x] << " " << revy[y] << endl;
    }
};

struct rectangle
{
    point A, B;

    rectangle()
    {
        A = point();
        B = point();
    }
    void input()
    {
        A.input();
        B.input();
    }
} r[maxn];

int n, k;
void input()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
        r[i].input();
}

vector < int > pos_x, pos_y;



bool inside(pair < int, int > cur, rectangle rec)
{
    if (cur.first >= rec.A.x && cur.first <= rec.B.x &&
            cur.second >= rec.A.y && cur.second <= rec.B.y)
        return true;
    return false;
}



void solve1()
{
    int min_x = 1e9, max_x = 1, min_y = 1e9, max_y = 1;
    for (int i = 1; i <= n; i ++)
    {
        min_x = min(min_x, r[i].B.x);
        max_x = max(max_x, r[i].A.x);
        min_y = min(min_y, r[i].B.y);
        max_y = max(max_y, r[i].A.y);
    }

    cout << revx[min_x] << " " << revy[min_y] << endl;
}

int used[maxn];

pair < point, point > solve2()
{
    int min_x = 1e9, max_x = 1, min_y = 1e9, max_y = 1;

    for (int i = 1; i <= n; i ++)
    {
        if (used[i])
            continue;

        min_x = min(min_x, r[i].B.x);
        max_x = max(max_x, r[i].A.x);
        min_y = min(min_y, r[i].B.y);
        max_y = max(max_y, r[i].A.y);
    }

    if (min_x > max_x && min_y > max_y)
    {
        return {point(max_x, max_y), point(max_x, max_y)};
    }

    vector < point > cell;
    cell.push_back(point(min_x, min_y));
    cell.push_back(point(min_x, max_y));
    cell.push_back(point(max_x, min_y));
    cell.push_back(point(max_x, max_y));

    ///cout << min_x << " " << max_x << " " << min_y << " " << max_y << endl;
    for (point d : cell)
        for (point f : cell)
        {
            bool done = true;
            for (int i = 1; i <= n; i ++)
            {
                if (used[i])
                    continue;
                if (!inside({d.x, d.y}, r[i]) && !inside({f.x, f.y}, r[i]))
                {
                    done = false;
                    break;
                }
            }

            if (done)
            {
                return {d, f};
                /**cout << d.x << " " << d.y << endl;
                cout << f.x << " " << f.y << endl;
                return;*/
            }
        }

    return {point(-1, -1), point(-1, -1)};
}

struct sol3
{
    point A, B, C;
    sol3(point _A, point _B, point _C)
    {
        A = _A;
        B = _B;
        C = _C;
    }
};
sol3 solve3()
{
    //for (int i = 1; i <= n; i ++)
      //  cout << r[i].A.x << " " << r[i].A.y << " " << r[i].B.x << " " << r[i].B.y << endl;
    int min_x = 1e9, max_x = 1, min_y = 1e9, max_y = 1;
    for (int i = 1; i <= n; i ++)
    {
        if (used[i])
            continue;

        min_x = min(min_x, r[i].B.x);
        max_x = max(max_x, r[i].A.x);
        min_y = min(min_y, r[i].B.y);
        max_y = max(max_y, r[i].A.y);
    }

    vector < point > cell;
    cell.push_back(point(min_x, min_y));
    cell.push_back(point(min_x, max_y));
    cell.push_back(point(max_x, min_y));
    cell.push_back(point(max_x, max_y));

    for (point cur : cell)
    {
        for (int i = 1; i <= n; i ++)
        {
            if (used[i])
                continue;
            if (inside({cur.x, cur.y}, r[i]))
                used[i] = 2;
        }

        pair < point, point > ans = solve2();
        for (int i = 1; i <= n; i ++)
        {
            if (used[i] == 2)
                used[i] = 0;
        }
        if (ans.first.x == -1)
            continue;

        return sol3(cur, ans.first, ans.second);
        /**cout << cur.x << " " << cur.y << endl;
        cout << ans.first.x << " " << ans.first.y << endl;
        cout << ans.second.x << " " << ans.second.y << endl;
        return;*/
    }
    return sol3(point(-1, -1), point(-1, -1), point(-1, -1));
}

void solve4()
{
    int min_x = 1e9, max_x = 1, min_y = 1e9, max_y = 1;
    for (int i = 1; i <= n; i ++)
    {
        min_x = min(min_x, r[i].B.x);
        max_x = max(max_x, r[i].A.x);
        min_y = min(min_y, r[i].B.y);
        max_y = max(max_y, r[i].A.y);
    }
    if (min_x > max_x)
        swap(min_x, max_x);
    if (min_y > max_y)
        swap(min_y, max_y);

    vector < point > cell;
    cell.push_back(point(min_x, min_y));
    cell.push_back(point(min_x, max_y));
    cell.push_back(point(max_x, min_y));
    cell.push_back(point(max_x, max_y));


    for (point cur : cell)
    {
        for (int i = 1; i <= n; i ++)
        {
            if (used[i])
                continue;
            if (inside({cur.x, cur.y}, r[i]))
                used[i] = 3;
        }

        sol3 ans = solve3();
        for (int i = 1; i <= n; i ++)
        {
            if (used[i] == 3)
                used[i] = 0;
        }
        if (ans.A.x == -1)
            continue;

        cout << revx[cur.x] << " " << revy[cur.y] << endl;
        ans.A.print();
        ans.B.print();
        ans.C.print();
        return;
        /**cout << cur.x << " " << cur.y << endl;
        cout << ans.first.x << " " << ans.first.y << endl;
        cout << ans.second.x << " " << ans.second.y << endl;
        return;*/
    }
}


void compress()
{
    vector < int > px;
    for (int i = 1; i <= n; i ++)
    {
        px.push_back(r[i].A.x);
        px.push_back(r[i].B.x);
    }

    sort(px.begin(), px.end());


    for (int i = 0; i < 2 * n; i ++)
    {
        ///cout << px[i] << " " << i << endl;
        mx[px[i]] = i + 1, revx[i + 1] = px[i];
    }
    //for (int i = 1; i <= 2 * n; i ++)
      //  cout << i << " " << rev[i] << endl;
    for (int i = 1; i <= n; i ++)
    {
        r[i].A.x = mx[r[i].A.x];
        r[i].B.x = mx[r[i].B.x];
    }

        vector < int > py;
    for (int i = 1; i <= n; i ++)
    {
        py.push_back(r[i].A.y);
        py.push_back(r[i].B.y);
    }

    sort(py.begin(), py.end());


    for (int i = 0; i < 2 * n; i ++)
        my[py[i]] = i + 1, revy[i + 1] = py[i];

    for (int i = 1; i <= n; i ++)
    {
        r[i].A.y = my[r[i].A.y];
        r[i].B.y = my[r[i].B.y];
    }
}
void solve()
{
    input();
    compress();
    if (k == 1)
        solve1();
    if (k == 2)
    {
        pair < point, point > ans = solve2();
        ans.first.print();
        ans.second.print();
    }
    if (k == 3)
    {
        sol3 res = solve3();
        res.A.print();
        res.B.print();
        res.C.print();
    }
    if (k == 4)
    {
        solve4();
    }

}

int main()
{
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}
/**
634025969 413050209
458184763 724583533
351907664 172518940

*/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct
4 Correct 5 ms 4700 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 5 ms 4688 KB Output is correct
4 Correct 5 ms 4700 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4792 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 5 ms 4708 KB Output is correct
4 Correct 5 ms 4700 KB Output is correct
5 Correct 5 ms 4700 KB Output is correct
6 Correct 6 ms 4700 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 7 ms 4960 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 5 ms 4816 KB Output is correct
11 Correct 5 ms 4700 KB Output is correct
12 Correct 5 ms 4700 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct
4 Correct 5 ms 4708 KB Output is correct
5 Correct 5 ms 4700 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 5 ms 4692 KB Output is correct
10 Correct 8 ms 4700 KB Output is correct
11 Correct 5 ms 4700 KB Output is correct
12 Correct 5 ms 4816 KB Output is correct
13 Correct 5 ms 4700 KB Output is correct
14 Incorrect 5 ms 4692 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct
4 Correct 5 ms 4700 KB Output is correct
5 Correct 635 ms 82152 KB Output is correct
6 Correct 604 ms 82628 KB Output is correct
7 Correct 601 ms 82008 KB Output is correct
8 Correct 715 ms 82068 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 5 ms 4688 KB Output is correct
4 Correct 5 ms 4700 KB Output is correct
5 Correct 645 ms 82056 KB Output is correct
6 Correct 754 ms 82124 KB Output is correct
7 Correct 680 ms 82144 KB Output is correct
8 Correct 693 ms 81952 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4792 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 5 ms 4708 KB Output is correct
4 Correct 5 ms 4700 KB Output is correct
5 Correct 5 ms 4700 KB Output is correct
6 Correct 6 ms 4700 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 7 ms 4960 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 5 ms 4816 KB Output is correct
11 Correct 5 ms 4700 KB Output is correct
12 Correct 5 ms 4700 KB Output is correct
13 Correct 690 ms 82076 KB Output is correct
14 Correct 614 ms 82096 KB Output is correct
15 Correct 621 ms 82360 KB Output is correct
16 Correct 752 ms 82080 KB Output is correct
17 Correct 662 ms 82104 KB Output is correct
18 Correct 733 ms 82096 KB Output is correct
19 Correct 706 ms 82172 KB Output is correct
20 Correct 629 ms 82032 KB Output is correct
21 Correct 659 ms 82140 KB Output is correct
22 Correct 683 ms 82100 KB Output is correct
23 Correct 634 ms 82100 KB Output is correct
24 Correct 629 ms 81956 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct
4 Correct 5 ms 4708 KB Output is correct
5 Correct 5 ms 4700 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 5 ms 4692 KB Output is correct
10 Correct 8 ms 4700 KB Output is correct
11 Correct 5 ms 4700 KB Output is correct
12 Correct 5 ms 4816 KB Output is correct
13 Correct 5 ms 4700 KB Output is correct
14 Incorrect 5 ms 4692 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -