Submission #858565

#	Time	Username	Problem	Language	Result	Execution time	Memory
858565		ofrankel	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	444 ms	15376 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()
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]);}
    if(sx==n+1)sx=0;if(sy==n+1)sy=0;
    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(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);
    for(auto&[i,j]:toz)cout<<indx[i]<<" "<<indy[j]<<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:8:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    8 |     if(sx==n+1)sx=0;if(sy==n+1)sy=0;
      |     ^~
hamburg.cpp:8:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    8 |     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: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79