Submission #230000

#	Time	Username	Problem	Language	Result	Execution time	Memory
230000		MarcoMeijer	Hamburg Steak (JOI20_hamburg)	C++14	15 / 100	133 ms	3704 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()

//===================//
//  Added libraries  //
//===================//

//===================//
//end added libraries//
//===================//

void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}


//===================//
//   begin program   //
//===================//

const int MX = 3e5;
int n, L[MX], R[MX], U[MX], D[MX];
bitset<MX> used;

void place(int x, int y) {
    RE(i,n) {
        if(L[i] <= x && x <= R[i] && U[i] <= y && y <= D[i]) used[i] = 1;
    }
}
bool solve(int k) {
    bitset<MX> curUsed = used;
    int maxL=0, minR=INF, maxU=0, minD=INF;
    RE(i,n) {
        if(used[i]) continue;
        maxL = max(maxL, L[i]);
        minR = min(minR, R[i]);
        maxU = max(maxU, U[i]);
        minD = min(minD, D[i]);
    }
    if(k == 1) {
        place(maxL, maxU);
        if(used.count() == n) {
            cout<<maxL<<" "<<maxU<<endl;
            return 1;
        }
        return 0;
    }
    if(k == 2) {
        place(minR, minD);
        if(solve(1)) {
            cout<<minR<<" "<<minD<<endl;
            return 1;
        }
        used = curUsed;
        place(minR, maxU);
        if(solve(1)) {
            cout<<minR<<" "<<maxU<<endl;
            return 1;
        }
        return 0;
    }
    if(k == 3) {
        place(minR, minD);
        if(solve(2)) {
            cout<<minR<<" "<<minD<<endl;
            return 1;
        }
        used = curUsed;
        place(minR, maxU);
        if(solve(2)) {
            cout<<minR<<" "<<maxU<<endl;
            return 1;
        }
        used = curUsed;
        place(maxL, minD);
        if(solve(2)) {
            cout<<maxL<<" "<<minD<<endl;
            return 1;
        }
        used = curUsed;
        place(maxL, maxU);
        if(solve(2)) {
            cout<<maxL<<" "<<maxU<<endl;
            return 1;
        }
        return 0;
    }
    if(k == 4) {
        RE(i,n) {
            if(minD <= U[i] && U[i] <= maxU) {
                place(minR, U[i]);
                if(solve(3)) {
                    cout<<minR<<" "<<U[i]<<endl;
                    return 1;
                }
                used = curUsed;
            }
            if(minD <= D[i] && D[i] <= maxU) {
                place(minR, D[i]);
                if(solve(3)) {
                    cout<<minR<<" "<<D[i]<<endl;
                    return 1;
                }
                used = curUsed;
            }
        }
        return 0;
    }
    return 0;
}

void program() {
    int k;
    cin>>n>>k;
    RE(i,n) cin>>L[i]>>U[i]>>R[i]>>D[i];
    used.reset();
    solve(k);
}

Compilation message (stderr)

hamburg.cpp: In function 'bool solve(int)':
hamburg.cpp:65:25: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |         if(used.count() == n) {
      |            ~~~~~~~~~~~~~^~~~

• 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