Submission #289976

#	Time	Username	Problem	Language	Result	Execution time	Memory
289976		gs18115	Hamburg Steak (JOI20_hamburg)	C++14	21 / 100	3024 ms	14224 KiB

hamburg

#include<iostream>
#include<vector>
#include<random>
#include<ctime>
#include<tuple>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
inline bool check(const pair<pi,pi>&sq,const pi&p)
{
    return sq.fi.fi<=p.fi&&p.fi<=sq.fi.se&&sq.se.fi<=p.se&&p.se<=sq.se.se;
}
inline pi get1(const vector<pair<pi,pi> >&v)
{
    int xmx=-inf,ymx=-inf;
    for(auto&t:v)
        xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi);
    return pi(xmx,ymx);
}
inline pair<pi,pi>get2(const vector<pair<pi,pi> >&v)
{
    int xmx=-inf,xmn=inf,ymx=-inf,ymn=inf;
    for(auto&t:v)
        xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi),
        xmn=min(xmn,t.fi.se),ymn=min(ymn,t.se.se);
    pi p[4]={pi(xmx,ymx),pi(xmx,ymn),pi(xmn,ymn),pi(xmn,ymx)};
    for(int i=0;i<2;i++)
    {
        int j=i+2;
        bool f=1;
        for(auto&t:v)
        {
            if(!check(t,p[i])&&!check(t,p[j]))
            {
                f=0;
                break;
            }
        }
        if(f)
            return pair<pi,pi>(p[i],p[j]);
    }
    return pair<pi,pi>(pi(-1,-1),pi(-1,-1));
}
tuple<pi,pi,pi>get3(const vector<pair<pi,pi> >&v)
{
    int xmx=-inf,xmn=inf,ymx=-inf,ymn=inf;
    for(auto&t:v)
        xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi),
        xmn=min(xmn,t.fi.se),ymn=min(ymn,t.se.se);
    vector<pi>pv({pi(xmx,ymx),pi(xmx,ymn),pi(xmn,ymx),pi(xmn,ymn)});
    for(pi&p:pv)
    {
        vector<pair<pi,pi> >nxv;
        for(auto&t:v)
            if(!check(t,p))
                nxv.eb(t);
        auto cget=get2(nxv);
        if(cget.fi.fi!=-1)
            return tuple<pi,pi,pi>(p,cget.fi,cget.se);
    }
    return tuple<pi,pi,pi>(pi(-1,-1),pi(-1,-1),pi(-1,-1));
}
tuple<pi,pi,pi,pi>get4(const vector<pair<pi,pi> >&v)
{
    int xmx=-inf,xmn=inf,ymx=-inf,ymn=inf;
    for(auto&t:v)
        xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi),
        xmn=min(xmn,t.fi.se),ymn=min(ymn,t.se.se);
    vector<pi>pv({pi(xmx,ymx),pi(xmx,ymn),pi(xmn,ymx),pi(xmn,ymn)});
    for(pi&p:pv)
    {
        vector<pair<pi,pi> >nxv;
        for(auto&t:v)
            if(!check(t,p))
                nxv.eb(t);
        auto cget=get3(nxv);
        if(get<0>(cget).fi!=-1)
            return tuple<pi,pi,pi,pi>(p,get<0>(cget),get<1>(cget),get<2>(cget));
    }
    return tuple<pi,pi,pi,pi>(pi(-1,-1),pi(-1,-1),pi(-1,-1),pi(-1,-1));
}
tuple<pi,pi,pi,pi>get4_rand(const vector<pair<pi,pi> >&v)
{
    int xmx=-inf,xmn=inf,ymx=-inf,ymn=inf;
    for(auto&t:v)
        xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi),
        xmn=min(xmn,t.fi.se),ymn=min(ymn,t.se.se);
    vector<pi>pv;
    for(auto&t:v)
        if(t.fi.fi<=xmn)
            pv.eb(xmn,t.se.fi);
    mt19937 gen(time(NULL));
    for(int i=0;i<(int)pv.size();i++)
        swap(pv[i],pv[i+gen()%((int)pv.size()-i)]);
    for(pi&p:pv)
    {
        vector<pair<pi,pi> >nxv;
        for(auto&t:v)
            if(!check(t,p))
                nxv.eb(t);
        auto cget=get3(nxv);
        if(get<0>(cget).fi!=-1)
            return tuple<pi,pi,pi,pi>(p,get<0>(cget),get<1>(cget),get<2>(cget));
    }
    return tuple<pi,pi,pi,pi>(pi(-1,-1),pi(-1,-1),pi(-1,-1),pi(-1,-1));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<pair<pi,pi> >v(n);
    for(auto&t:v)
        cin>>t.fi.fi>>t.se.fi>>t.fi.se>>t.se.se;
    if(k==1)
    {
        pi ans=get1(v);
        cout<<ans.fi<<' '<<ans.se<<endl;
        return 0;
    }
    if(k==2)
    {
        auto ans=get2(v);
        cout<<ans.fi.fi<<' '<<ans.fi.se<<' '<<ans.se.fi<<' '<<ans.se.se<<endl;
        return 0;
    }
    if(k==3)
    {
        auto ans=get3(v);
        cout<<get<0>(ans).fi<<' '<<get<0>(ans).se<<endl;
        cout<<get<1>(ans).fi<<' '<<get<1>(ans).se<<endl;
        cout<<get<2>(ans).fi<<' '<<get<2>(ans).se<<endl;
        return 0;
    }
    {
        auto ans=get4(v);
        if(get<0>(ans).fi!=-1)
        {
            cout<<get<0>(ans).fi<<' '<<get<0>(ans).se<<endl;
            cout<<get<1>(ans).fi<<' '<<get<1>(ans).se<<endl;
            cout<<get<2>(ans).fi<<' '<<get<2>(ans).se<<endl;
            cout<<get<3>(ans).fi<<' '<<get<3>(ans).se<<endl;
            return 0;
        }
    }
    auto ans=get4_rand(v);
    cout<<get<0>(ans).fi<<' '<<get<0>(ans).se<<endl;
    cout<<get<1>(ans).fi<<' '<<get<1>(ans).se<<endl;
    cout<<get<2>(ans).fi<<' '<<get<2>(ans).se<<endl;
    cout<<get<3>(ans).fi<<' '<<get<3>(ans).se<<endl;
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79