oj.uz

Submission #858567

# Submission time Handle Problem Language Result Execution time Memory
858567 2023-10-08T20:52:37 Z ofrankel Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 351 ms 7656 KB 
#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]);max1=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(type3[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(b1&&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;return 0;}
    return 0;
}

Compilation message

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Incorrect 4 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 301 ms 5904 KB Output is correct
6 Correct 304 ms 5864 KB Output is correct
7 Correct 299 ms 5884 KB Output is correct
8 Correct 298 ms 5880 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 317 ms 6740 KB Output is correct
6 Correct 330 ms 6484 KB Output is correct
7 Correct 320 ms 6632 KB Output is correct
8 Correct 318 ms 6652 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 307 ms 7432 KB Output is correct
14 Correct 305 ms 7412 KB Output is correct
15 Correct 306 ms 7436 KB Output is correct
16 Correct 318 ms 7656 KB Output is correct
17 Correct 307 ms 7252 KB Output is correct
18 Correct 308 ms 7432 KB Output is correct
19 Correct 319 ms 7436 KB Output is correct
20 Correct 327 ms 7504 KB Output is correct
21 Correct 351 ms 7432 KB Output is correct
22 Correct 335 ms 7476 KB Output is correct
23 Correct 330 ms 7548 KB Output is correct
24 Correct 316 ms 7476 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Incorrect 4 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -