Submission #880963

#TimeUsernameProblemLanguageResultExecution timeMemory
880963abcvuitunggioHamburg Steak (JOI20_hamburg)C++17
2 / 100
69 ms14056 KiB
#include <bits/stdc++.h> using namespace std; const int INF=1e9; int n,k,l[200001],d[200001],r[200001],u[200001],cnt[10],cnt2[10]; vector <pair <int, int>> res,v; vector <int> a,b; vector <int> f(vector <pair <int, int>> ve){ vector <int> v; while (!ve.empty()){ int mx=0; for (auto [l,r]:ve) mx=max(mx,l); v.push_back(mx); vector <pair <int, int>> tmp; for (auto [l,r]:ve) if (l>mx||r<mx) tmp.push_back({l,r}); swap(ve,tmp); } return v; } void backtrack(int pos, int k){ if (pos==a.size()*b.size()){ int ch=1; for (int i=0;i<a.size();i++) if (!cnt[i]) ch=0; for (int i=0;i<b.size();i++) if (!cnt2[i]) ch=0; if (ch){ for (int i=0;i<n;i++){ int c=0; for (auto [x,y]:res) if (l[i]<=x&&r[i]>=x&&d[i]<=y&&u[i]>=y){ c=1; break; } if (!c) return; } for (auto [x,y]:res) cout << x << ' ' << y << '\n'; while (k--) cout << 1 << ' ' << 1 << '\n'; exit(0); } return; } int i=pos/b.size(),j=pos%b.size(); backtrack(pos+1,k); if (k){ cnt[i]++; cnt2[j]++; res.push_back({a[i],b[j]}); backtrack(pos+1,k-1); cnt[i]--; cnt2[j]--; res.pop_back(); } } 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({l[i],r[i]}); } a=f(v); v.clear(); for (int i=0;i<n;i++) v.push_back({d[i],u[i]}); b=f(v); backtrack(0,k); }

Compilation message (stderr)

hamburg.cpp: In function 'void backtrack(int, int)':
hamburg.cpp:23:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if (pos==a.size()*b.size()){
      |         ~~~^~~~~~~~~~~~~~~~~~~
hamburg.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int i=0;i<a.size();i++)
      |                      ~^~~~~~~~~
hamburg.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i=0;i<b.size();i++)
      |                      ~^~~~~~~~~
#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...