Submission #880921

#	Time	Username	Problem	Language	Result	Execution time	Memory
880921		abcvuitunggio	Hamburg Steak (JOI20_hamburg)	C++17	6 / 100	76 ms	11396 KiB

hamburg

#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-=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<2;i++)
            for (int j=0;j<2;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 (stderr)

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: In function 'int main()':
hamburg.cpp:76:10: warning: unused variable 'tmp' [-Wunused-variable]
   76 |     bool tmp=solve(v,k);
      |          ^~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79