oj.uz

답안 #896926

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

        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 ++)
        {
            used[i] = inside({cur.x, cur.y}, r[i]);
        }

        pair < point, point > ans = solve2();
        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()
{

}

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

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 3 ms 4700 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

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

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 3 ms 4696 KB Output is correct
3 Correct 3 ms 4704 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4696 KB Output is correct
6 Correct 3 ms 4704 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 4 ms 4696 KB Output is correct
12 Correct 3 ms 4700 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 3 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 228 ms 9116 KB Output is correct
6 Correct 237 ms 9044 KB Output is correct
7 Correct 235 ms 8992 KB Output is correct
8 Correct 248 ms 8960 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 4 ms 4700 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 237 ms 9000 KB Output is correct
6 Correct 239 ms 8960 KB Output is correct
7 Correct 238 ms 9104 KB Output is correct
8 Correct 231 ms 8940 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 3 ms 4696 KB Output is correct
3 Correct 3 ms 4704 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4696 KB Output is correct
6 Correct 3 ms 4704 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 5 ms 4700 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 4 ms 4696 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 242 ms 8860 KB Output is correct
14 Correct 231 ms 8980 KB Output is correct
15 Correct 234 ms 8864 KB Output is correct
16 Correct 243 ms 9056 KB Output is correct
17 Correct 230 ms 8868 KB Output is correct
18 Correct 241 ms 8928 KB Output is correct
19 Correct 221 ms 8788 KB Output is correct
20 Correct 219 ms 8880 KB Output is correct
21 Correct 234 ms 8860 KB Output is correct
22 Correct 229 ms 8916 KB Output is correct
23 Correct 230 ms 9044 KB Output is correct
24 Correct 233 ms 9044 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 -