Submission #1066186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066186		phong	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	310 ms	26784 KiB

hamburg

#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 (stderr)

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 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79