Submission #308280

#TimeUsernameProblemLanguageResultExecution timeMemory
308280cki86201Hamburg Steak (JOI20_hamburg)C++17
15 / 100
471 ms13536 KiB
#include <bits/stdc++.h> using namespace std; #define Fi first #define Se second typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define all(x) (x).begin(), (x).end() #define pb push_back #define szz(x) (int)(x).size() #define rep(i, n) for(int i=0;i<(n);i++) typedef tuple<int, int, int> t3; const int INF = 1e9 + 10, M = 4e5 + 5; int N, K; vector <int> vx, vy; struct rect { int x1, y1, x2, y2; bool In(int x, int y) { return x1 <= x && x <= x2 && y1 <= y && y <= y2; } } R[200020]; void trial(vector <pii> ans) { if(szz(ans) == 0 || szz(ans) > K) return; while(szz(ans) < K) ans.pb(ans[0]); for(int i=1;i<=N;i++) { int r = 0; for(auto &[x, y] : ans) if(R[i].In(x, y)) { r = 1; break; } if(r == 0) return; } for(auto [x, y] : ans) printf("%d %d\n", vx[x-1], vy[y-1]); exit(0); } int arr[4*M+5]; vector <int> solve_linear(vector <pii> R) { for(int i=1;i<=M;i++) arr[i] = INF; for(auto [x, y] : R) arr[x] = min(arr[x], y); for(int i=M-1;i;i--) arr[i] = min(arr[i], arr[i+1]); vector <int> res; for(int t=1;arr[t]!=INF;t=arr[t]+1) res.pb(arr[t]); return res; } void solve(vector <int> rst, int k, vector <pii> ans) { if(szz(rst) == 0) trial(ans); if(k == 0) return; int lx = INF, rx = -INF, ly = INF, ry = -INF; for(int i : rst) { lx = min(lx, R[i].x2); rx = max(rx, R[i].x1); ly = min(ly, R[i].y2); ry = max(ry, R[i].y1); } if(k == 1) { if(lx >= rx && ly >= ry) { ans.pb({rx, ry}); trial(ans); } return; } if(lx >= rx) { vector <pii> V; for(int i : rst) V.pb({R[i].y1, R[i].y2}); auto ys = solve_linear(V); for(int y : ys) ans.pb({rx, y}); trial(ans); return; } if(ly >= ry) { vector <pii> V; for(int i : rst) V.pb({R[i].x1, R[i].x2}); auto xs = solve_linear(V); for(int x : xs) ans.pb({x, ry}); trial(ans); return; } vector <pii> vert; for(int x : {lx, rx}) for(int y : {ly, ry}) vert.pb({x, y}); for(auto [x, y] : vert) { vector <int> nst; for(int i : rst) if(!R[i].In(x, y)) nst.pb(i); auto ans2 = ans; ans2.pb({x, y}); solve(nst, k - 1, ans2); } } int main() { scanf("%d%d", &N, &K); if(K == 4) return 0; for(int i=1;i<=N;i++) { scanf("%d%d%d%d", &R[i].x1, &R[i].y1, &R[i].x2, &R[i].y2); vx.pb(R[i].x1), vx.pb(R[i].x2); vy.pb(R[i].y1), vy.pb(R[i].y2); } sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin()); sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin()); for(int i=1;i<=N;i++) { auto &[x1, y1, x2, y2] = R[i]; x1 = (int)(lower_bound(all(vx), x1) - vx.begin()) + 1; y1 = (int)(lower_bound(all(vy), y1) - vy.begin()) + 1; x2 = (int)(lower_bound(all(vx), x2) - vx.begin()) + 1; y2 = (int)(lower_bound(all(vy), y2) - vy.begin()) + 1; } vector <int> rst; for(int i=1;i<=N;i++) rst.pb(i); solve(rst, K, {}); return 0; }

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   scanf("%d%d%d%d", &R[i].x1, &R[i].y1, &R[i].x2, &R[i].y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...