Submission #858568

#	Time	Username	Problem	Language	Result	Execution time	Memory
858568		ofrankel	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	547 ms	21760 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()
void gtmn(int &x,int y){if(y<x)x=y;}
void gtmx(int &x,int y){if(y>x)x=y;}
vector<pair<int,int>>rec(int n,int k,vector<int>&l,vector<int>&d,vector<int>&r,vector<int>&u,vector<int>&was){
    int sx=n+1,sy=n+1,bx=0,by=0;for(int i=0;n>i;++i)if(!was[i]){sx=min(sx,r[i]);bx=max(bx,l[i]);sy=min(sy,u[i]);by=max(by,d[i]);}
    //small x,small y,big x,big y
    if(sx==n+1)sx=0;if(sy==n+1)sy=0;
    //for k=1,(sx,sy) should work
    if(k==1){for(int i=0;n>i;++i)if(!was[i])if(!(l[i]<=sx&&sx<=r[i]&&d[i]<=sy&&sy<=u[i]))return {};return {{sx,sy}};}
    
    //for other k values, one of the four options should work
    for(int x:{sx,bx})for(int y:{sy,by}){
        
        vector<int>was2=was;
        for(int i=0;n>i;++i)if(!was2[i])if(l[i]<=x&&x<=r[i]&&d[i]<=y&&y<=u[i])was2[i]=1;
        auto v=rec(n,k-1,l,d,r,u,was2);
        if(v.size()){v.push_back({x,y});return v;}
    }
    return {};
}
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>l(n),d(n),r(n),u(n);
    for(int i=0;n>i;++i)cin>>l[i]>>d[i]>>r[i]>>u[i];
    vector<int>indx=l;sort(all(indx));indx.resize(unique(all(indx))-indx.begin());
    vector<int>indy=d;sort(all(indy));indy.resize(unique(all(indy))-indy.begin());
    for(int i=0;n>i;++i){l[i]=lower_bound(all(indx),l[i])-indx.begin();r[i]=upper_bound(all(indx),r[i])-indx.begin()-1;
        d[i]=lower_bound(all(indy),d[i])-indy.begin();u[i]=upper_bound(all(indy),u[i])-indy.begin()-1;
    }
    vector<int>was(n,0);
    vector<pair<int,int>>toz=rec(n,k,l,d,r,u,was);
    if(toz.size()){for(auto&[i,j]:toz)cout<<indx[i]<<" "<<indy[j]<<endl;return 0;}
    
    int sx=n+1,sy=n+1,bx=0,by=0;for(int i=0;n>i;++i)if(!was[i]){sx=min(sx,r[i]);bx=max(bx,l[i]);sy=min(sy,u[i]);by=max(by,d[i]);}
    int h=indy.size(),w=indx.size();
    vector<int>type1(w,h),type2(w,h);
    int min_u=h;
    vector<int>to_down_st(h,0),to_down_en(h,h);
    vector<int>to_left_st(w,0),to_left_en(w,w),to_right_st(w,0),to_right_en(w,w);
    vector<int>type3(h,w),type4(h,0);
    int min1=sy+1,max1=by-1,min2=sx+1,max2=bx-1,min3=sy+1,max3=by-1,min4=sx+1,max4=bx-1;
    for(int i=0;n>i;++i){
        bool b1=l[i]<=sx,b2=d[i]<=sy,b3=r[i]>=bx,b4=u[i]>=by;
        if(b1+b2+b3+b4>=3)continue;
        if(b1+b2+b3+b4==1){
            if(b1){min1=max(min1,d[i]);max1=min(max1,u[i]);}
            else if(b3){min3=max(min3,d[i]);max3=min(max3,u[i]);}
            else if(b2){min2=max(min2,l[i]);max2=min(max2,r[i]);}
            else if(b4){min4=max(min4,l[i]);max4=min(max4,r[i]);}
        }
        else{
            if(b1&&b2)gtmn(type1[r[i]+1],u[i]);
            else if(b2&&b3)gtmn(type2[l[i]-1],u[i]);
            else if(b1&&b4)gtmn(type3[d[i]-1],r[i]);
            else if(b3&&b4)gtmx(type4[d[i]-1],l[i]);
            else if(b1&&b3){min_u=min(min_u,u[i]);gtmx(to_down_st[d[i]-1],d[i]);gtmn(to_down_en[d[i]-1],u[i]);}
            else if(b2&&b4){gtmn(to_left_en[l[i]-1],r[i]);gtmx(to_left_st[l[i]-1],l[i]);
                gtmn(to_right_en[r[i]+1],r[i]);gtmx(to_right_st[r[i]+1],l[i]);
            }
        }
    }
    for(int i=sx+1;bx>=i;++i){gtmn(type1[i],type1[i-1]);gtmn(to_right_en[i],to_right_en[i-1]);gtmx(to_right_st[i],to_right_st[i-1]);}
    for(int i=bx-1;i>=sx;--i){gtmn(type2[i],type2[i+1]);gtmn(to_left_en[i],to_left_en[i+1]);gtmx(to_left_st[i],to_left_st[i+1]);}
    for(int i=by-1;i>=sy;--i){gtmn(type3[i],type3[i+1]);gtmx(type4[i],type4[i+1]);
        gtmn(to_down_en[i],to_down_en[i+1]);gtmx(to_down_st[i],to_down_st[i+1]);}
    
    for(int num2=min2;max2>=num2;++num2){
        int cmax1=min(max1,type1[num2]);
        int cmax3=min(max3,type2[num2]);
        int cmin4=max({min4,to_right_st[num2],to_left_st[num2]});
        int cmax4=min({max4,to_right_en[num2],to_left_en[num2]});
        //opt1
        int num1=min(cmax1,min_u);
        int cmin3=max(min3,to_down_st[num1]);
        int num3=min(cmax3,to_down_en[num1]);
        if(num3>=cmin3&&num1>=min1){
            int ccmin4=max(cmin4,type4[num3]);
            int ccmax4=min(cmax4,type3[num1]);
            if(ccmax4>=ccmin4){toz={{sx,num1},{num2,sy},{bx,num3},{ccmin4,by}};}
        }
        //opt2
        num3=min(cmax3,min_u);
        int cmin1=max(min1,to_down_st[num3]);
        num1=min(cmax1,to_down_en[num3]);
        if(num3>=min3&&num1>=cmin1){
            int ccmin4=max(cmin4,type4[num3]);
            int ccmax4=min(cmax4,type3[num1]);
            if(ccmax4>=ccmin4){toz={{sx,num1},{num2,sy},{bx,num3},{ccmin4,by}};}
        }
    }
    if(toz.size()){for(auto&[i,j]:toz)cout<<indx[i]<<" "<<indy[j]<<endl;}
   // for(auto&[i,j]:toz)cout<<i<<" "<<j<<endl;
    //for(int i=0;n>i;++i){bool b=0;for(auto [j,q]:toz)if(l[i]<=j&&j<=r[i]&&d[i]<=q&&q<=u[i])b=1;if(!b)cout<<l[i]<<" "<<d[i]<<" "<<r[i]<<" "<<u[i]<<endl;}
    return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'std::vector<std::pair<int, int> > rec(int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
hamburg.cpp:11:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   11 |     if(sx==n+1)sx=0;if(sy==n+1)sy=0;
      |     ^~
hamburg.cpp:11:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   11 |     if(sx==n+1)sx=0;if(sy==n+1)sy=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: 79 / 79