oj.uz

Submission #896930

# Submission time Handle Problem Language Result Execution time Memory
896930 2024-01-02T11:15:15 Z danikoynov Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 244 ms 4952 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;
    }

};

struct point
{
    int x, y;

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

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

    void print()
    {
        cout << x << " " << 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;

const int maxk = 5;

const int maxs = maxk * maxk;
pair < int, int > skew[maxs];
int m;
bitset < maxn > skew_set[maxs];

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 match_pairs()
{
    ///cout << pos_x.size() << " : " << pos_y.size() << endl;
    for (int x : pos_x)
        for (int y : pos_y)
            skew[++ m] = {x, y};

    for (int i = 1; i <= m; i ++)
        for (int j = 1; j <= n; j ++)
            skew_set[i][j] = inside(skew[i], r[j]);

}

void find_skewers()
{
    if (k == 1)
    {
        assert(m == 1);
        cout << skew[1].first << " " << skew[1].second << endl;
        return;
    }

    if (k == 2)
    {
        ///cout << pos_x.size() << " : " << pos_y.size() << endl;
        for (int i = 1; i <= m; i ++)
            for (int j = i; j <= m; j ++)
            {
                if ((skew_set[i] | skew_set[j]).count() == n)
                {
                    cout << skew[i].first << " " << skew[i].second << endl;
                    cout << skew[j].first << " " << skew[j].second << endl;
                    return;
                }
            }

        ///assert(false);
    }

    if (k == 3)
    {
        for (int i = 1; i <= m; i ++)
        {
            pair < int, int > cur = skew[i];
            //cout << cur.first << " " << cur.second << endl;
        }

        bitset < maxn > temp;
        for (int i = 1; i < m; i ++)
        {
            for (int j = i; j <= m; j ++)
                for (int f = j; f <= m; f ++)
                {
                    temp = (skew_set[i] | skew_set[j]);
                    temp = (temp | skew_set[f]);
                    ///cout << temp.count() << "  " << n << " " << n - temp.count() << endl;
                    if (temp.count() == n)
                    {
                        cout << skew[i].first << " " << skew[i].second << endl;
                        cout << skew[j].first << " " << skew[j].second << endl;
                        cout << skew[f].first << " " << skew[f].second << endl;
                        return;
                    }
                }
        }
    }
}
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 << min_x << " " << 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()
{
    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);
    }
    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 << cur.x << " " << 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 solve()
{
    input();
    if (k == 1)
        solve1();
    if (k == 2)
    {
        pair < point, point > ans = solve2();
        cout << ans.first.x << " " << ans.first.y << endl;
        cout << ans.second.x << " " << ans.second.y << endl;
    }
    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

*/

Compilation message

hamburg.cpp: In function 'void find_skewers()':
hamburg.cpp:133:57: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  133 |                 if ((skew_set[i] | skew_set[j]).count() == n)
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
hamburg.cpp:148:31: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  148 |             pair < int, int > cur = skew[i];
      |                               ^~~
hamburg.cpp:161:38: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  161 |                     if (temp.count() == n)
      |                         ~~~~~~~~~~~~~^~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 4 ms 4700 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 3 ms 4840 KB Output is correct
5 Correct 3 ms 4696 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct
8 Correct 4 ms 4876 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 3 ms 4804 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 4 ms 4700 KB Output is correct
14 Incorrect 4 ms 4700 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 3 ms 4700 KB Output is correct
2 Correct 3 ms 4696 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 212 ms 4892 KB Output is correct
6 Correct 212 ms 4700 KB Output is correct
7 Correct 219 ms 4768 KB Output is correct
8 Correct 210 ms 4696 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4792 KB Output is correct
5 Correct 219 ms 4700 KB Output is correct
6 Correct 239 ms 4696 KB Output is correct
7 Correct 212 ms 4700 KB Output is correct
8 Correct 211 ms 4696 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 3 ms 4792 KB Output is correct
3 Correct 3 ms 4696 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4696 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 3 ms 4696 KB Output is correct
10 Correct 3 ms 4700 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 221 ms 4944 KB Output is correct
14 Correct 214 ms 4768 KB Output is correct
15 Correct 216 ms 4772 KB Output is correct
16 Correct 220 ms 4944 KB Output is correct
17 Correct 224 ms 4944 KB Output is correct
18 Correct 227 ms 4768 KB Output is correct
19 Correct 218 ms 4764 KB Output is correct
20 Correct 229 ms 4768 KB Output is correct
21 Correct 229 ms 4772 KB Output is correct
22 Correct 244 ms 4768 KB Output is correct
23 Correct 220 ms 4780 KB Output is correct
24 Correct 228 ms 4768 KB Output is correct

Subtask #8
0 / 79.0

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