oj.uz

Submission #880927

# Submission time Handle Problem Language Result Execution time Memory
880927 2023-11-30T08:52:02 Z abcvuitunggio Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 78 ms 14632 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;
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]);
    }
    vector <int> a,b;
    a.push_back(mn);
    b.push_back(mn2);
    if (mn<mx)
        a.push_back(mx);
    if (mn2<mx2)
        b.push_back(mx2);
    if ((a.size()==1||b.size()==1)&&k<=2){
        k-=a.size()*b.size();
        for (int i:a)
            for (int j:b)
                res.push_back({i,j});
        while (k--)
            res.push_back({1,1});
        return true;
    }
    if (k==1)
        return false;
    if (k==2){
        for (int i=0;i<2;i++){
            int ch=0;
            for (int j:v)
                ch+=((l[j]<=a[0]&&a[0]<=r[j]&&d[j]<=b[i]&&b[i]<=u[j])||(l[j]<=a[1]&&a[1]<=r[j]&&d[j]<=b[i^1]&&b[i^1]<=u[j]));
            if (ch==v.size()){
                res.push_back({a[0],b[i]});
                res.push_back({a[1],b[i^1]});
                return true;
            }
        }
        return false;
    }
    if (k==3){
        for (int i=0;i<a.size();i++)
            for (int j=0;j<b.size();j++){
                vector <int> v2;
                for (int k:v)
                    if (l[k]>a[i]||r[k]<a[i]||d[k]>b[j]||u[k]<b[j])
                        v2.push_back(k);
                if (solve(v2,k-1)){
                    res.push_back({a[i],b[j]});
                    return true;
                }
            }
        return false;
    }
    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 'bool solve(std::vector<int>, int)':
hamburg.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if (ch==v.size()){
      |                 ~~^~~~~~~~~~
hamburg.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int i=0;i<a.size();i++)
      |                      ~^~~~~~~~~
hamburg.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for (int j=0;j<b.size();j++){
      |                          ~^~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:76:10: warning: unused variable 'tmp' [-Wunused-variable]
   76 |     bool tmp=solve(v,k);
      |          ^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2604 KB Output is correct
3 Correct 1 ms 2536 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2596 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 2396 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 Incorrect 1 ms 2392 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5072 KB Output is correct
6 Correct 60 ms 5068 KB Output is correct
7 Correct 61 ms 5232 KB Output is correct
8 Correct 63 ms 5072 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 62 ms 5104 KB Output is correct
6 Correct 61 ms 5076 KB Output is correct
7 Correct 61 ms 5068 KB Output is correct
8 Correct 78 ms 5184 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2604 KB Output is correct
3 Correct 1 ms 2536 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2596 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 66 ms 13664 KB Output is correct
14 Correct 65 ms 13588 KB Output is correct
15 Correct 62 ms 13388 KB Output is correct
16 Correct 66 ms 13392 KB Output is correct
17 Correct 64 ms 13560 KB Output is correct
18 Correct 62 ms 13264 KB Output is correct
19 Correct 67 ms 14128 KB Output is correct
20 Correct 66 ms 13828 KB Output is correct
21 Correct 78 ms 14632 KB Output is correct
22 Correct 73 ms 14504 KB Output is correct
23 Correct 68 ms 14244 KB Output is correct
24 Correct 71 ms 14420 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -