oj.uz

답안 #896928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896928 2024-01-02T11:14:01 Z danikoynov 함박 스테이크 (JOI20_hamburg) C++14
15 / 100
 270 ms 4948 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));
}

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)
      |                         ~~~~~~~~~~~~~^~~~
hamburg.cpp: In function 'sol3 solve3()':
hamburg.cpp:288:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  288 |         if (ans.first.x == -1)
      |         ^~
hamburg.cpp:291:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  291 |             return sol3(cur, ans.first, ans.second);
      |             ^~~~~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 3 ms 4792 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 5 ms 4796 KB Output is correct

Subtask #2
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 4 ms 4700 KB Output is correct
3 Correct 3 ms 4696 KB Output is correct
4 Correct 3 ms 4696 KB Output is correct

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4696 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 3 ms 4696 KB Output is correct
4 Correct 5 ms 4696 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 4 ms 4696 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 4 ms 4796 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 3 ms 4700 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 4 ms 4796 KB Output is correct

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4700 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 3 ms 4792 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 5 ms 4796 KB Output is correct
5 Correct 219 ms 4700 KB Output is correct
6 Correct 228 ms 4700 KB Output is correct
7 Correct 270 ms 4700 KB Output is correct
8 Correct 223 ms 4700 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 4 ms 4700 KB Output is correct
3 Correct 3 ms 4696 KB Output is correct
4 Correct 3 ms 4696 KB Output is correct
5 Correct 226 ms 4948 KB Output is correct
6 Correct 230 ms 4764 KB Output is correct
7 Correct 229 ms 4768 KB Output is correct
8 Correct 225 ms 4700 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4696 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 3 ms 4696 KB Output is correct
4 Correct 5 ms 4696 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 4 ms 4696 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 4 ms 4796 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 3 ms 4700 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 4 ms 4796 KB Output is correct
13 Correct 253 ms 4948 KB Output is correct
14 Correct 225 ms 4764 KB Output is correct
15 Correct 235 ms 4948 KB Output is correct
16 Correct 228 ms 4772 KB Output is correct
17 Correct 227 ms 4768 KB Output is correct
18 Correct 230 ms 4944 KB Output is correct
19 Correct 238 ms 4768 KB Output is correct
20 Correct 235 ms 4772 KB Output is correct
21 Correct 232 ms 4944 KB Output is correct
22 Correct 255 ms 4768 KB Output is correct
23 Correct 231 ms 4768 KB Output is correct
24 Correct 266 ms 4768 KB Output is correct

Subtask #8
0 / 79.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4700 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -