oj.uz

Submission #858565

# Submission time Handle Problem Language Result Execution time Memory
858565 2023-10-08T19:34:16 Z ofrankel Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 444 ms 15376 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;}
    }
    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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 4 ms 468 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 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 3 ms 348 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 3 ms 348 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 5 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 3 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 5 ms 348 KB Output is correct
14 Incorrect 5 ms 348 KB Unexpected end of file - int32 expected
15 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 344 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 302 ms 5904 KB Output is correct
6 Correct 310 ms 5792 KB Output is correct
7 Correct 335 ms 6124 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 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 325 ms 6700 KB Output is correct
6 Correct 329 ms 6480 KB Output is correct
7 Correct 319 ms 6632 KB Output is correct
8 Correct 320 ms 6900 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 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 3 ms 348 KB Output is correct
9 Correct 5 ms 600 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 325 ms 15200 KB Output is correct
14 Correct 339 ms 15068 KB Output is correct
15 Correct 330 ms 15200 KB Output is correct
16 Correct 321 ms 15180 KB Output is correct
17 Correct 338 ms 15376 KB Output is correct
18 Correct 365 ms 15208 KB Output is correct
19 Correct 338 ms 15196 KB Output is correct
20 Correct 333 ms 15188 KB Output is correct
21 Correct 363 ms 15196 KB Output is correct
22 Correct 444 ms 15188 KB Output is correct
23 Correct 349 ms 15184 KB Output is correct
24 Correct 338 ms 15168 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 5 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 3 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 5 ms 348 KB Output is correct
14 Incorrect 5 ms 348 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -