Submission #308284

#TimeUsernameProblemLanguageResultExecution timeMemory
308284cki86201Hamburg Steak (JOI20_hamburg)C++17
15 / 100
618 ms38008 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; pii operator+(pii a, pii b) { return {max(a.Fi, b.Fi), min(a.Se, b.Se)}; } 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, int flp = 0) { 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) { if(flp) y = szz(vy) + 1 - y; 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; } pii seg[6][2][M+5]; 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); } if(k != 4) return; auto fy = [&](int &y) { y = szz(vy) + 1 - y; }; auto Intersect = [&](const rect &a, const rect &b) { pii x = pii(a.x1, a.x2) + pii(b.x1, b.x2); if(x.Fi > x.Se) return 0; pii y = pii(a.y1, a.y2) + pii(b.y1, b.y2); if(y.Fi > y.Se) return 0; return 1; }; auto solve4 = [&](int flp) { rect Side[4]; Side[0] = {lx, ly, lx, ry}; Side[1] = {lx, ry, rx, ry}; Side[2] = {rx, ly, rx, ry}; Side[3] = {lx, ly, rx, ly}; auto type = [&](int t) { int res = 0; rep(i, 4) if(Intersect(R[t], Side[i])) res |= 1<<i; return res; }; pii Seg[4]; Seg[0] = Seg[2] = {ly, ry}; Seg[1] = Seg[3] = {lx, rx}; auto upd = [&](pii &a, pii b) { a = a + b; }; rep(i, 6) rep(j, 2) rep(k, M+1) seg[i][j][k] = pii(-INF, INF); int nrx = INF; for(int i=1;i<=N;i++) { int t = type(i); pii wx = {R[i].x1, R[i].x2}, wy = {R[i].y1, R[i].y2}; if(t == 1) upd(Seg[0], wy); else if(t == 2) upd(Seg[1], wx); else if(t == 4) upd(Seg[2], wy); else if(t == 8) upd(Seg[3], wx); else if(t == 3) upd(seg[0][0][R[i].y1-1], wx); else if(t == 5) { upd(seg[1][0][R[i].y1-1], wy); upd(seg[1][1][R[i].y2+1], wy); } else if(t == 9) upd(seg[2][1][R[i].y2+1], wx); else if(t == 6) upd(seg[3][0][R[i].x1-1], wy); else if(t == 10) { upd(seg[4][0][R[i].x1-1], wx); upd(seg[4][1][R[i].x2+1], wx); nrx = min(nrx, R[i].x2); } } rep(i, 6) { for(int j=M-1;j;j--) upd(seg[i][0][j], seg[i][0][j+1]); for(int j=2;j<=M;j++) upd(seg[i][1][j], seg[i][1][j-1]); for(int j=1;j<=M;j++) upd(seg[i][0][j], seg[i][1][j]); } vector <pii> ans(4); for(int i=ly+1;i<ry;i++) { ans[0] = {lx, i}; pii NS[3]; rep(j, 3) NS[j] = Seg[j+1] + seg[j][0][i]; int ri = min({nrx, NS[0].Se, NS[2].Se}); if(NS[0].Fi > NS[0].Se) continue; ans[1] = {ri, ry}; upd(NS[1], seg[3][0][ri]); upd(NS[2], seg[4][0][ri]); if(NS[1].Fi > NS[1].Se) continue; int rj = NS[1].Fi; ans[2] = {rx, rj}; upd(NS[2], seg[5][0][rj]); if(NS[2].Fi > NS[2].Se) continue; ans[3] = {NS[2].Se, ly}; trial(ans); } }; solve4(0); for(int i=1;i<=N;i++) fy(R[i].y1), fy(R[i].y2); swap(ly, ry); fy(ly), fy(ry); solve4(1); } int main() { scanf("%d%d", &N, &K); 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:175:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  175 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  177 |   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...