oj.uz

Submission #1066186

# Submission time Handle Problem Language Result Execution time Memory
1066186 2024-08-19T16:10:19 Z phong Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 310 ms 26784 KB 
#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e6 + 5, N = 1e6;
const ll oo = 1e9 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, k;
vector<int> nen;
struct node{
    int x1, y1, x2, y2;
}a[nmax];
vector<pii> ans;
void check(){
    for(int i = 1; i <= n; ++i){
        bool ok = 0;
        for(auto [x, y] : ans){
            if(a[i].x1 <= x && x <= a[i].x2 && a[i].y1 <= y &&  y <= a[i].y2){
                ok = 1;
            }
        }
        if(!ok) return;
    }
    while(ans.size() < k) ans.push_back(ans[0]);
    for(auto [x, y] : ans) cout << nen[x] << ' ' << nen[y] << endl;
    exit(0);
}
namespace sub1{
    void sol(){
        int ma = -oo, ma_2 =-oo;
        for(int i = 1; i <= n; ++i){
            ma = max(ma, a[i].x1);
            ma_2 = max(ma_2, a[i].y1);
        }
        cout << nen[ma] << ' ' << nen[ma_2];
    }
}
namespace sub2{
    pii tx = {1, 1};
    void dfs(int K, vector<node> a){
        int y1 = oo, y2 = -oo, x1 = oo, x2 =-oo;
        for(int i = 0; i < a.size(); ++i){
            y1 = min(y1, a[i].y2);
            y2 = max(y2, a[i].y1);
            x1 = min(x1, a[i].x2);
            x2 = max(x2, a[i].x1);
        }

        vector<pii> tmp;
        tmp.push_back({x1, y1});
        tmp.push_back({x1, y2});
        tmp.push_back({x2, y1});
        tmp.push_back({x2, y2});
        if(K == 2){
            ans.push_back(tx);
            check();
            for(int i = 0; i < tmp.size(); ++i){
                for(int j = i + 1; j <= tmp.size(); ++j){
                    ans.clear();
                    if(k == 3)ans.push_back(tx);
                    ans.push_back(tmp[i]);
                    ans.push_back(tmp[j]);
                    check();
                }
            }
            return;
        }
        vector<node> rev;
        for(auto [x, y] : tmp){
            rev.clear();
            tx = {x, y};
            for(auto p : a){
                if(p.x1 <= x && x <= p.x2 && p.y1 <= y && y <= p.y2)continue;
                rev.push_back(p);
            }
            dfs(k - 1, rev);
        }
    }
    void sol(){
        vector<node> tmp;
        for(int i = 1; i <= n; ++i) tmp.push_back(a[i]);
        dfs(k, tmp);
    }
}
namespace sub3{

}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >>a[i].y2;
        nen.push_back(a[i].x1);
        nen.push_back(a[i].y1);
        nen.push_back(a[i].x2);
        nen.push_back(a[i].y2);
    }
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    for(int i = 1; i <= n; ++i){
        a[i].x1 = lower_bound(nen.begin(), nen.end(), a[i].x1) - nen.begin();
        a[i].y1 = lower_bound(nen.begin(), nen.end(), a[i].y1) - nen.begin();
        a[i].x2 = lower_bound(nen.begin(), nen.end(), a[i].x2) - nen.begin();
        a[i].y2 = lower_bound(nen.begin(), nen.end(), a[i].y2) - nen.begin();
    }
    if(k == 1) return sub1::sol(),0;
    if(k == 2 ||k == 3) return sub2::sol(), 0;
//    sub3::sol();
}
/*

3
1 2 3 4 5 6
7 8 9 10 11
*/

Compilation message

hamburg.cpp: In function 'void check()':
hamburg.cpp:31:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     while(ans.size() < k) ans.push_back(ans[0]);
      |           ~~~~~~~~~~~^~~
hamburg.cpp: In function 'void sub2::dfs(int, std::vector<node>)':
hamburg.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i = 0; i < a.size(); ++i){
      |                        ~~^~~~~~~~~~
hamburg.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int i = 0; i < tmp.size(); ++i){
      |                            ~~^~~~~~~~~~~~
hamburg.cpp:65:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 for(int j = i + 1; j <= tmp.size(); ++j){
      |                                    ~~^~~~~~~~~~~~~
hamburg.cpp: At global scope:
hamburg.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main(){
      | ^~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 568 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 476 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 230 ms 14396 KB Output is correct
6 Correct 250 ms 14528 KB Output is correct
7 Correct 230 ms 14432 KB Output is correct
8 Correct 229 ms 14360 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 250 ms 20612 KB Output is correct
6 Correct 284 ms 20848 KB Output is correct
7 Correct 310 ms 20832 KB Output is correct
8 Correct 228 ms 20804 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 568 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 258 ms 24136 KB Output is correct
14 Correct 248 ms 24000 KB Output is correct
15 Correct 301 ms 22644 KB Output is correct
16 Correct 251 ms 22656 KB Output is correct
17 Correct 247 ms 24092 KB Output is correct
18 Correct 253 ms 22340 KB Output is correct
19 Correct 248 ms 24420 KB Output is correct
20 Correct 245 ms 24392 KB Output is correct
21 Correct 250 ms 26784 KB Output is correct
22 Correct 243 ms 26696 KB Output is correct
23 Correct 248 ms 26696 KB Output is correct
24 Correct 293 ms 26692 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -