oj.uz

Submission #748039

# Submission time Handle Problem Language Result Execution time Memory
748039 2023-05-25T10:27:34 Z doowey Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 407 ms 30716 KB 
#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

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.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 8 ms 464 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 7 ms 596 KB Output is correct
10 Correct 4 ms 572 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 3 ms 596 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 472 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 4 ms 652 KB Output is correct
14 Incorrect 4 ms 664 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 299 ms 17528 KB Output is correct
6 Correct 336 ms 17544 KB Output is correct
7 Correct 347 ms 17488 KB Output is correct
8 Correct 328 ms 17668 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 496 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 302 ms 20600 KB Output is correct
6 Correct 313 ms 20472 KB Output is correct
7 Correct 312 ms 20688 KB Output is correct
8 Correct 294 ms 23556 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 8 ms 464 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 7 ms 596 KB Output is correct
10 Correct 4 ms 572 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 296 ms 20976 KB Output is correct
14 Correct 286 ms 21264 KB Output is correct
15 Correct 285 ms 19708 KB Output is correct
16 Correct 271 ms 19792 KB Output is correct
17 Correct 272 ms 23044 KB Output is correct
18 Correct 277 ms 20280 KB Output is correct
19 Correct 272 ms 23772 KB Output is correct
20 Correct 271 ms 24260 KB Output is correct
21 Correct 368 ms 30716 KB Output is correct
22 Correct 351 ms 26016 KB Output is correct
23 Correct 323 ms 28276 KB Output is correct
24 Correct 407 ms 29452 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 472 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 4 ms 652 KB Output is correct
14 Incorrect 4 ms 664 KB Output isn't correct
15 Halted 0 ms 0 KB -