Submission #232728

#	Time	Username	Problem	Language	Result	Execution time	Memory
232728		medk	Hamburg Steak (JOI20_hamburg)	C++14	15 / 100	178 ms	18784 KiB

hamburg

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()

using namespace std;

const int MAXN=2e5;

struct rect
{
    int U,D,L,R;
};

vector<pair<int,int>> solveK1(vector<rect> v)
{
    int H[2]={1,(int)1e9},V[2]={1,(int)1e9};
    for(rect tmp:v)
    {
        H[0]=max(H[0],tmp.L);
        H[1]=min(H[1],tmp.R);
        V[0]=max(V[0],tmp.D);
        V[1]=min(V[1],tmp.U);
    }
    if(H[0]<=H[1] && V[0]<=V[1]) return  {{H[0],V[0]}};
    else return {};
}

vector<pair<int,int>> solveK2(vector<rect> v)
{
    int H[2]={1,(int)1e9},V[2]={1,(int)1e9};
    for(rect tmp:v)
    {
        H[0]=max(H[0],tmp.L);
        H[1]=min(H[1],tmp.R);
        V[0]=max(V[0],tmp.D);
        V[1]=min(V[1],tmp.U);
    }
    for(int x:{0,1})
        for(int y:{0,1})
        {
            vector<rect> tosend;
            for(rect tmp:v)
            {
                if(H[x]>=tmp.L && H[x]<=tmp.R && V[y]>=tmp.D && V[y]<=tmp.U) continue;
                tosend.pb(tmp);
            }
            vector<pair<int,int>> get=solveK1(tosend);
            if(sz(get)==0) continue;
            return {{H[x],V[y]},get[0]};
        }
    return {};
}


vector<pair<int,int>> solveK3(vector<rect> v)
{
    int H[2]={1,(int)1e9},V[2]={1,(int)1e9};
    for(rect tmp:v)
    {
        H[0]=max(H[0],tmp.L);
        H[1]=min(H[1],tmp.R);
        V[0]=max(V[0],tmp.D);
        V[1]=min(V[1],tmp.U);
    }
    for(int x:{0,1})
        for(int y:{0,1})
        {
            vector<rect> tosend;
            for(rect tmp:v)
            {
                if(H[x]>=tmp.L && H[x]<=tmp.R && V[y]>=tmp.D && V[y]<=tmp.U) continue;
                tosend.pb(tmp);
            }
            vector<pair<int,int>> get=solveK2(tosend);
            if(sz(get)==0) continue;
            return {{H[x],V[y]},get[0],get[1]};
        }
    return {};
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int n,k; cin>>n>>k;
    vector<rect> v;
    rect tmp;
    for(int i=0;i<n;i++)
    {
        cin>>tmp.L>>tmp.D>>tmp.R>>tmp.U;
        v.pb(tmp);
    }
    vector<pair<int,int>> ans;
    if(k==1) ans=solveK1(v);
    if(k==2) ans=solveK2(v);
    if(k==3) ans=solveK3(v);
    for(pair<int,int> pt:ans) cout<<pt.x<<' '<<pt.y<<'\n';
    return 0;
}

• 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