oj.uz

답안 #896911

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

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;
}

void solve2()
{
    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));

    ///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 (!inside({d.x, d.y}, r[i]) && !inside({f.x, f.y}, r[i]))
            {
                done = false;
                break;
            }
        }

        if (done)
        {
            cout << d.x << " " << d.y << endl;
            cout << f.x << " " << f.y << endl;
            return;
        }
    }
}
void solve()
{
    input();
    if (k == 1)
        solve1();
    if (k == 2)
    solve2();

}

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:128:57: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  128 |                 if ((skew_set[i] | skew_set[j]).count() == n)
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
hamburg.cpp:143:31: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  143 |             pair < int, int > cur = skew[i];
      |                               ^~~
hamburg.cpp:156:38: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  156 |                     if (temp.count() == n)
      |                         ~~~~~~~~~~~~~^~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
0 / 3.0

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

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3928 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 3932 KB Output is correct
2 Correct 3 ms 3932 KB Output is correct
3 Correct 3 ms 3932 KB Output is correct
4 Correct 5 ms 3932 KB Output is correct
5 Correct 211 ms 3980 KB Output is correct
6 Correct 216 ms 3980 KB Output is correct
7 Correct 210 ms 3980 KB Output is correct
8 Correct 217 ms 3980 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3932 KB Output is correct
2 Correct 3 ms 3932 KB Output is correct
3 Correct 4 ms 3932 KB Output is correct
4 Correct 5 ms 3932 KB Output is correct
5 Correct 236 ms 8072 KB Output is correct
6 Correct 218 ms 8144 KB Output is correct
7 Correct 225 ms 8072 KB Output is correct
8 Correct 220 ms 8080 KB Output is correct

Subtask #7
0 / 6.0

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

Subtask #8
0 / 79.0

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