oj.uz

Submission #787470

# Submission time Handle Problem Language Result Execution time Memory
787470 2023-07-19T08:18:41 Z 반딧불(#10031) Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 259 ms 11564 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
bool check1();
bool check2();
bool check3();
bool check4();
void output();

int main(){
    input();
    if(!check1()) if(!check2()) if(!check3()) check4();
    output();
}

int n, k;
vector<int> xCoord(1), yCoord(1);
int L[200002], R[200002], D[200002], U[200002], X, Y;
vector<pair<int, int> > ans;

void input(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d %d", &L[i], &D[i], &R[i], &U[i]);
        xCoord.push_back(L[i]); xCoord.push_back(R[i]);
        yCoord.push_back(D[i]); yCoord.push_back(U[i]);
    }
    sort(xCoord.begin(), xCoord.end()); xCoord.erase(unique(xCoord.begin(), xCoord.end()), xCoord.end());
    sort(yCoord.begin(), yCoord.end()); yCoord.erase(unique(yCoord.begin(), yCoord.end()), yCoord.end());
    for(int i=1; i<=n; i++){
        L[i] = lower_bound(xCoord.begin(), xCoord.end(), L[i]) - xCoord.begin();
        R[i] = lower_bound(xCoord.begin(), xCoord.end(), R[i]) - xCoord.begin();
        D[i] = lower_bound(yCoord.begin(), yCoord.end(), D[i]) - yCoord.begin();
        U[i] = lower_bound(yCoord.begin(), yCoord.end(), U[i]) - yCoord.begin();
    }
    X = (int)xCoord.size()-1, Y = (int)yCoord.size()-1;
}

bool check1(){
    int maxX = 0, maxY = 0;
    for(int i=1; i<=n; i++) maxX = max(maxX, L[i]), maxY = max(maxY, D[i]);
    for(int i=1; i<=n; i++){
        if(maxX > R[i] || maxY > U[i]) return false;
    }
    ans.push_back(make_pair(maxX, maxY));
    return true;
}

struct namespace2{
    bool tryWith(int x, int y){
        int maxL = 1, maxD = 1, minR = X, minU = Y;
        for(int i=1; i<=n; i++){
            if(L[i] <= x && x <= R[i] && D[i] <= y && y <= U[i]) continue;
            maxL = max(maxL, L[i]), maxD = max(maxD, D[i]);
            minR = min(minR, R[i]), minU = min(minU, U[i]);
        }
        if(maxL <= minR && maxD <= minU){
            ans.push_back(make_pair(x, y));
            ans.push_back(make_pair(maxL, maxD));
            return true;
        }
        return false;
    }

    bool check2(){
        int maxL = *max_element(L+1, L+n+1);
        int minR = *min_element(R+1, R+n+1);
        int maxD = *max_element(D+1, D+n+1);
        int minU = *min_element(U+1, U+n+1);
        if(tryWith(maxL, maxD)) return true;
        if(tryWith(maxL, minU)) return true;
        if(tryWith(minR, maxD)) return true;
        if(tryWith(minR, minU)) return true;
        return false;
    }
} p2;

bool check2(){
    return p2.check2();
}

struct namespace3{
    bool check2(int n, vector<int> &L, vector<int> &R, vector<int> &D, vector<int> &U, int px, int py){
        int maxL = *max_element(L.begin(), L.end());
        int minR = *min_element(R.begin(), R.end());
        int maxD = *max_element(D.begin(), D.end());
        int minU = *min_element(U.begin(), U.end());
        int Xd[2] = {maxL, minR}, Yd[2] = {maxD, minU};
        for(int a: Xd) for(int b: Yd){
            int maxL = 1, maxD = 1, minR = X, minU = Y;
            for(int i=0; i<n; i++){
                if(L[i] <= a && a <= R[i] && D[i] <= b && b <= U[i]) continue;
                maxL = max(maxL, L[i]), maxD = max(maxD, D[i]);
                minR = min(minR, R[i]), minU = min(minU, U[i]);
            }
            if(maxL <= minR && maxD <= minU){
                ans.push_back(make_pair(px, py));
                ans.push_back(make_pair(a, b));
                ans.push_back(make_pair(maxL, maxD));
                return true;
            }
        }
        return false;
    }

    bool tryWith(int x, int y){
        vector<int> _L,_R,_D,_U;
        for(int i=1; i<=n; i++){
            if(L[i]<=x && x<=R[i] && D[i]<=y && y<=U[i]) continue;
            else _L.push_back(L[i]), _R.push_back(R[i]), _D.push_back(D[i]), _U.push_back(U[i]);
        }
        return check2((int)_L.size(),_L,_R,_D,_U,x,y);
    }

    bool check3(){
        int maxL = *max_element(L+1, L+n+1);
        int minR = *min_element(R+1, R+n+1);
        int maxD = *max_element(D+1, D+n+1);
        int minU = *min_element(U+1, U+n+1);
        if(tryWith(maxL, maxD)) return true;
        if(tryWith(maxL, minU)) return true;
        if(tryWith(minR, maxD)) return true;
        if(tryWith(minR, minU)) return true;
        return false;
    }
} p3;

bool check3(){
    return p3.check3();
}

bool check4(){
    return false;
}

void output(){
    if(ans.empty()) exit(1);
    while((int)ans.size() < k) ans.push_back(ans.back());
    for(auto p: ans) printf("%d %d\n", xCoord[p.first], yCoord[p.second]);
}

Compilation message

hamburg.cpp: In function 'void input()':
hamburg.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d %d %d %d", &L[i], &D[i], &R[i], &U[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 340 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 235 ms 6776 KB Output is correct
6 Correct 234 ms 6776 KB Output is correct
7 Correct 230 ms 6780 KB Output is correct
8 Correct 236 ms 6772 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 236 ms 6748 KB Output is correct
6 Correct 245 ms 6840 KB Output is correct
7 Correct 233 ms 6684 KB Output is correct
8 Correct 240 ms 6780 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 242 ms 9228 KB Output is correct
14 Correct 255 ms 9524 KB Output is correct
15 Correct 242 ms 9456 KB Output is correct
16 Correct 238 ms 8904 KB Output is correct
17 Correct 236 ms 9420 KB Output is correct
18 Correct 241 ms 8056 KB Output is correct
19 Correct 245 ms 11128 KB Output is correct
20 Correct 259 ms 11564 KB Output is correct
21 Correct 249 ms 11240 KB Output is correct
22 Correct 248 ms 11564 KB Output is correct
23 Correct 258 ms 11408 KB Output is correct
24 Correct 249 ms 11260 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 340 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -