oj.uz

Submission #858564

# Submission time Handle Problem Language Result Execution time Memory
858564 2023-10-08T19:33:00 Z ofrankel Hamburg Steak (JOI20_hamburg) C++17
6 / 100
 361 ms 6652 KB 
#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

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.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 344 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 4 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 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 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Runtime error 4 ms 600 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 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 600 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Runtime error 3 ms 604 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
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 344 KB Output is correct
5 Correct 297 ms 6132 KB Output is correct
6 Correct 295 ms 5712 KB Output is correct
7 Correct 361 ms 5884 KB Output is correct
8 Correct 299 ms 5900 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 4 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 311 ms 6480 KB Output is correct
6 Correct 308 ms 6484 KB Output is correct
7 Correct 303 ms 6636 KB Output is correct
8 Correct 311 ms 6652 KB Output is correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 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 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Runtime error 4 ms 600 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 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 600 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 364 KB Output is correct
9 Runtime error 3 ms 604 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -