oj.uz

Submission #881038

# Submission time Handle Problem Language Result Execution time Memory
881038 2023-11-30T11:49:17 Z abcvuitunggio Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 134 ms 18388 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,k,l[200001],d[200001],r[200001],u[200001];
vector <pair <int, int>> res;
vector <int> v;
vector <int> f(vector <int> v, int x, int y){
    vector <int> res;
    for (int i:v)
        if (l[i]>x||r[i]<x||d[i]>y||u[i]<y)
            res.push_back(i);
    return res;
}
bool solve(vector <int> v, int k){
    if (v.empty()){
        while (k--)
            res.push_back({1,1});
        return true;
    }
    if (!k)
        return false;
    int mn=INF,mx=0,mn2=INF,mx2=0;
    for (int i:v){
        mn=min(mn,r[i]);
        mx=max(mx,l[i]);
        mn2=min(mn2,u[i]);
        mx2=max(mx2,d[i]);
    }
    if (solve(f(v,mn,mn2),k-1)){
        res.push_back({mn,mn2});
        return true;
    }
    if (solve(f(v,mn,mx2),k-1)){
        res.push_back({mn,mx2});
        return true;
    }
    if (solve(f(v,mx,mn2),k-1)){
        res.push_back({mx,mn2});
        return true;
    }
    if (solve(f(v,mx,mx2),k-1)){
        res.push_back({mx,mx2});
        return true;
    }
    return false;
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> k;
    for (int i=0;i<n;i++){
        cin >> l[i] >> d[i] >> r[i] >> u[i];
        v.push_back(i);
    }
    bool tmp=solve(v,k);
    for (auto [x,y]:res)
        cout << x << ' ' << y << '\n';
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:54:10: warning: unused variable 'tmp' [-Wunused-variable]
   54 |     bool tmp=solve(v,k);
      |          ^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Incorrect 3 ms 2652 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 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 60 ms 5948 KB Output is correct
6 Correct 60 ms 5836 KB Output is correct
7 Correct 60 ms 5840 KB Output is correct
8 Correct 61 ms 5984 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 67 ms 6596 KB Output is correct
6 Correct 62 ms 6588 KB Output is correct
7 Correct 61 ms 6504 KB Output is correct
8 Correct 69 ms 8588 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 65 ms 14440 KB Output is correct
14 Correct 65 ms 14540 KB Output is correct
15 Correct 64 ms 14172 KB Output is correct
16 Correct 63 ms 14028 KB Output is correct
17 Correct 68 ms 14800 KB Output is correct
18 Correct 63 ms 14288 KB Output is correct
19 Correct 69 ms 15052 KB Output is correct
20 Correct 69 ms 15820 KB Output is correct
21 Correct 134 ms 18388 KB Output is correct
22 Correct 87 ms 16148 KB Output is correct
23 Correct 83 ms 17368 KB Output is correct
24 Correct 91 ms 17876 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Incorrect 3 ms 2652 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -