Submission #858564

#	Time	Username	Problem	Language	Result	Execution time	Memory
858564		ofrankel	Hamburg Steak (JOI20_hamburg)	C++17	6 / 100	361 ms	6652 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;}
    }
}
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)if(i>=indx.size()||j>=indy.size())cout<<"hi\n";else 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;
      |                     ^~
hamburg.cpp: In function 'int main()':
hamburg.cpp:31:28: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(auto&[i,j]:toz)if(i>=indx.size()||j>=indy.size())cout<<"hi\n";else cout<<indx[i]<<" "<<indy[j]<<endl;
      |                           ~^~~~~~~~~~~~~
hamburg.cpp:31:44: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(auto&[i,j]:toz)if(i>=indx.size()||j>=indy.size())cout<<"hi\n";else cout<<indx[i]<<" "<<indy[j]<<endl;
      |                                           ~^~~~~~~~~~~~~
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:17:1: warning: control reaches end of non-void function [-Wreturn-type]
   17 | }
      | ^

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