Submission #748039

#	Time	Username	Problem	Language	Result	Execution time	Memory
748039		doowey	Hamburg Steak (JOI20_hamburg)	C++14	15 / 100	407 ms	30716 KiB

hamburg

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);


const int M = (int)8e5 + 10;

struct Rect{
    int Li;
    int Di;
    int Ri;
    int Ui;
};

int maxL(vector<Rect> &x){
    int mx = -1;
    for(auto r : x) mx = max(mx, r.Li);
    return mx;
}

int minR(vector<Rect> &x){
    int mx = (int)1e9;
    for(auto r : x) mx = min(mx, r.Ri);
    return mx;
}

int maxD(vector<Rect> &x){
    int mx = -1;
    for(auto r : x) mx = max(mx, r.Di);
    return mx;
}

int minU(vector<Rect> &x){
    int mx = (int)1e9;
    for(auto r : x) mx = min(mx, r.Ui);
    return mx;
}

vector<int> pos;

int getId(int x){
    return lower_bound(pos.begin(), pos.end(), x) - pos.begin();
}

vector<pii> solve(vector<Rect> rr, int k){
    if(rr.empty()) {
        vector<pii> e;
        for(int i = 0 ; i < k ; i ++ ) e.push_back(mp(0,0));
        return e;
    }
    int mnR = minR(rr);
    int mxL = maxL(rr);
    int mnU = minU(rr);
    int mxD = maxD(rr);
    if(k == 1){
        if(mxL <= mnR && mxD <= mnU){
            return {mp(mxL, mxD)};
        }
        else{
            return {};
        }
    }
    vector<pii> e;
    e.push_back(mp(mnR, mnU));
    e.push_back(mp(mnR, mxD));
    e.push_back(mp(mxL, mnU));
    e.push_back(mp(mxL, mxD));
    for(auto c : e){
        vector<Rect> ss;
        for(auto r : rr){
            if(c.fi >= r.Li && c.fi <= r.Ri && c.se >= r.Di && c.se <= r.Ui){
                continue;
            }
            ss.push_back(r);
        }
        vector<pii> sol = solve(ss, k - 1);
        if(!sol.empty()){
            while(sol.size() < k) sol.push_back(c);
            return sol;
        }
    }
    return {};
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n, k;
    cin >> n >> k;
    vector<Rect> rr(n);
    int m;
    for(int i = 0 ; i < n; i ++ ){
        cin >> rr[i].Li >> rr[i].Di >> rr[i].Ri >> rr[i].Ui;
        pos.push_back(rr[i].Li);
        pos.push_back(rr[i].Di);
        pos.push_back(rr[i].Ri);
        pos.push_back(rr[i].Ui);
    }
    sort(pos.begin(), pos.end());
    pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
    m = pos.size();
    for(auto &r : rr){
        r.Li = getId(r.Li);
        r.Di = getId(r.Di);
        r.Ri = getId(r.Ri);
        r.Ui = getId(r.Ui);
    }
    vector<pii> Y = solve(rr, k);
    if(!Y.empty()){
        for(auto q : Y){
            cout << pos[q.fi] << " " << pos[q.se] << "\n";
        }
    }
    else{
        for(int i = 1; i <= k ; i ++ ){
            cout << 1 << " " << 1 << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'std::vector<std::pair<int, int> > solve(std::vector<Rect>, int)':
hamburg.cpp:86:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |             while(sol.size() < k) sol.push_back(c);
      |                   ~~~~~~~~~~~^~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:99:9: warning: variable 'm' set but not used [-Wunused-but-set-variable]
   99 |     int m;
      |         ^

• 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