oj.uz

Submission #787444

# Submission time Handle Problem Language Result Execution time Memory
787444 2023-07-19T07:59:55 Z 반딧불(#10031) Hamburg Steak (JOI20_hamburg) C++17
6 / 100
 238 ms 6840 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();
}

bool check3(){
    return false;
}

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 3 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
0 / 3.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 #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 3 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 226 ms 6660 KB Output is correct
6 Correct 236 ms 6776 KB Output is correct
7 Correct 233 ms 6840 KB Output is correct
8 Correct 229 ms 6704 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 231 ms 6776 KB Output is correct
6 Correct 229 ms 6700 KB Output is correct
7 Correct 238 ms 6716 KB Output is correct
8 Correct 226 ms 6700 KB Output is correct

Subtask #7
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 #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 -