oj.uz

Submission #858561

# Submission time Handle Problem Language Result Execution time Memory
858561 2023-10-08T19:24:12 Z ofrankel Hamburg Steak (JOI20_hamburg) C++17
6 / 100
 335 ms 14656 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(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)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:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Correct 3 ms 544 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 344 KB Output is correct
3 Correct 3 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 348 KB Output is correct
2 Correct 3 ms 544 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 452 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Runtime error 3 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 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 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 3 ms 704 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 4 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 307 ms 13540 KB Output is correct
6 Correct 306 ms 13652 KB Output is correct
7 Correct 311 ms 13412 KB Output is correct
8 Correct 304 ms 13652 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 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 335 ms 14308 KB Output is correct
6 Correct 327 ms 14420 KB Output is correct
7 Correct 320 ms 14420 KB Output is correct
8 Correct 323 ms 14656 KB Output is correct

Subtask #7
0 / 6.0

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