Submission #880770

#TimeUsernameProblemLanguageResultExecution timeMemory
880770abcvuitunggioHamburg Steak (JOI20_hamburg)C++17
6 / 100
76 ms13884 KiB
#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); for (int i=0;i<(1<<(a.size()));i++) for (int j=0;j<(1<<(b.size()));j++){ vector <pair <int, int>> tmp; for (int k=0;k<a.size();k++) for (int l=0;l<b.size();l++) if (((i>>k)&1)^((j>>l)&1)) tmp.push_back({a[k],b[l]}); if (max(a.size(),b.size())>tmp.size()||tmp.size()>k) continue; vector <int> v2; for (int i:v){ int ch=0; for (auto [x,y]:tmp) if (l[i]<=x&&x<=r[i]&&d[i]<=y&&y<=u[i]) ch=1; if (!ch) v2.push_back(i); } if (solve(v2,k-tmp.size())){ for (auto [x,y]:tmp) res.push_back({x,y}); 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 (stderr)

hamburg.cpp: In function 'bool solve(std::vector<int>, int)':
hamburg.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for (int k=0;k<a.size();k++)
      |                          ~^~~~~~~~~
hamburg.cpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 for (int l=0;l<b.size();l++)
      |                              ~^~~~~~~~~
hamburg.cpp:36:62: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |             if (max(a.size(),b.size())>tmp.size()||tmp.size()>k)
      |                                                    ~~~~~~~~~~^~
hamburg.cpp: In function 'int main()':
hamburg.cpp:62:10: warning: unused variable 'tmp' [-Wunused-variable]
   62 |     bool tmp=solve(v,k);
      |          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...