Submission #212542

#TimeUsernameProblemLanguageResultExecution timeMemory
212542eriksuenderhaufHamburg Steak (JOI20_hamburg)C++11
21 / 100
874 ms16904 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define trav(x,a) for (auto& x: a) #define sz(x) (int)(x).size() #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%I64d", &(n)) #define nai(a, n) for (int _i = 0; _i < (n); _i++) ni(a[_i]) #define nal(a, n) for (int _i = 0; _i < (n); _i++) nl(a[_i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%I64d\n", (n)) #define pii pair<int, int> #define pll pair<long long, long long> #define vii vector<pii> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define st first #define nd second #define ar array<int,4> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int mod = 1e9 + 7; const int inf = 1e9 + 7; const int N = 2e5 + 5; const double eps = 1e-9; bool ok(ar j, ar i) { return !(j[2] < i[0] || i[2] < j[0] || j[3] < i[1] || i[3] < j[1]); } bool ins(ar j, pii i) { return j[0] <= i.st && i.st <= j[2] && j[1] <= i.nd && i.nd <= j[3]; } bool val(ar i) { return i[0] <= i[2] && i[1] <= i[3]; } vii check(vector<ar>& a, int k, pii ed); vii solve1(vector<ar>& a) { int n = sz(a)-1; pii U, L, R, D; U = R = {inf, -1}; D = L = {-inf, -1}; for (int i = 1; i <= n; i++) { U = min(U, {a[i][3], i}); D = max(D, {a[i][1], i}); L = max(L, {a[i][0], i}); R = min(R, {a[i][2], i}); } if (val({L.st, D.st, R.st, U.st})) return {{L.st, D.st}}; return {}; } vii solve2(vector<ar>& a) { int n = sz(a)-1; pii U, L, R, D; U = R = {inf, -1}; D = L = {-inf, -1}; for (int i = 1; i <= n; i++) { U = min(U, {a[i][3], i}); D = max(D, {a[i][1], i}); L = max(L, {a[i][0], i}); R = min(R, {a[i][2], i}); } vii ans; ans = check(a, 1, mp(R.st, U.st)); if (!ans.empty()) return ans; ans = check(a, 1, mp(R.st, D.st)); if (!ans.empty()) return ans; ans = check(a, 1, mp(L.st, U.st)); if (!ans.empty()) return ans; ans = check(a, 1, mp(L.st, D.st)); if (!ans.empty()) return ans; return {}; } vii solve3(vector<ar>& a) { int n = sz(a)-1; pii U, L, R, D; U = R = {inf, -1}; D = L = {-inf, -1}; for (int i = 1; i <= n; i++) { U = min(U, {a[i][3], i}); D = max(D, {a[i][1], i}); L = max(L, {a[i][0], i}); R = min(R, {a[i][2], i}); } vii ans; ans = check(a, 2, mp(R.st, U.st)); if (!ans.empty()) return ans; ans = check(a, 2, mp(R.st, D.st)); if (!ans.empty()) return ans; ans = check(a, 2, mp(L.st, U.st)); if (!ans.empty()) return ans; ans = check(a, 2, mp(L.st, D.st)); if (!ans.empty()) return ans; return {}; } int crossV(ar i, int j) { return i[0] <= j && j <= i[2]; } int crossH(ar i, int j) { return i[1] <= j && j <= i[3]; } vii solve4(vector<ar>& a) { int n = sz(a)-1; pii U, L, R, D; U = R = {inf, -1}; D = L = {-inf, -1}; for (int i = 1; i <= n; i++) { U = min(U, {a[i][3], i}); D = max(D, {a[i][1], i}); L = max(L, {a[i][0], i}); R = min(R, {a[i][2], i}); } vii ans; ans = check(a, 3, mp(R.st, U.st)); if (!ans.empty()) return ans; ans = check(a, 3, mp(R.st, D.st)); if (!ans.empty()) return ans; ans = check(a, 3, mp(L.st, U.st)); if (!ans.empty()) return ans; ans = check(a, 3, mp(L.st, D.st)); if (!ans.empty()) return ans; ar lo, hi; for (int i = 0; i < 4; i++) lo[i] = inf, hi[i] = -inf; for (int i = 1; i <= n; i++) { int msk = (crossV(a[i], R.st) << 3) + (crossH(a[i], U.st) << 2) + (crossV(a[i], L.st) << 1) + (crossH(a[i], D.st) << 0); if (__builtin_popcount(msk) != 1) continue; int b = 0; if (msk & 1) b = 0; // D if (msk & 2) b = 1; // L if (msk & 4) b = 2; // U if (msk & 8) b = 3; // R lo[b] = min(lo[b], a[i][2 + (b & 1)]); hi[b] = max(hi[b], a[i][0 + (b & 1)]); } ans = check(a, 3, mp(R.st, lo[3])); if (!ans.empty()) return ans; ans = check(a, 3, mp(R.st, hi[3])); if (!ans.empty()) return ans; ans = check(a, 3, mp(L.st, lo[1])); if (!ans.empty()) return ans; ans = check(a, 3, mp(L.st, hi[1])); if (!ans.empty()) return ans; ans = check(a, 3, mp(lo[0], D.st)); if (!ans.empty()) return ans; ans = check(a, 3, mp(hi[0], D.st)); if (!ans.empty()) return ans; ans = check(a, 3, mp(lo[2], U.st)); if (!ans.empty()) return ans; ans = check(a, 3, mp(hi[2], U.st)); if (!ans.empty()) return ans; return {}; } vii check(vector<ar>& a, int k, pii ed) { int n = sz(a)-1; if (n <= k) { vii ret; for (int i = 1; i <= k; i++) ret.pb({a[i][0], a[i][1]}); return ret; } vector<ar> nx; nx.pb({0, 0, 0, 0}); for (int i = 1; i <= n; i++) if (!ins(a[i], ed)) nx.pb(a[i]); vii tmp; if (k == 1) tmp = solve1(nx); else if (k == 2) tmp = solve2(nx); else tmp = solve3(nx); if (!tmp.empty()) tmp.pb(ed); return tmp; } int main() { int n, k; scanf("%d %d", &n, &k); vector<ar> a(n+1); for (int i = 1; i <= n; i++) { for (int j = 0; j < 4; j++) scanf("%d", &a[i][j]); } if (n <= k) { for (int i = 1; i <= n; i++) printf("%d %d\n", a[i][0], a[i][1]); for (int i = n+1; i <= k; i++) printf("1 1\n"); return 0; } { vii ans = solve1(a); if (!ans.empty()) { while (sz(ans) < k) ans.pb({1, 1}); trav(x, ans) printf("%d %d\n", x.st, x.nd); return 0; } } { vii ans = solve2(a); if (!ans.empty()) { while (sz(ans) < k) ans.pb({1, 1}); trav(x, ans) printf("%d %d\n", x.st, x.nd); return 0; } } { vii ans = solve3(a); if (!ans.empty()) { while (sz(ans) < k) ans.pb({1, 1}); trav(x, ans) printf("%d %d\n", x.st, x.nd); return 0; } } { vii ans = solve4(a); if (!ans.empty()) { while (sz(ans) < k) ans.pb({1, 1}); trav(x, ans) printf("%d %d\n", x.st, x.nd); return 0; } } return 0; }

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:200:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  200 |   int n, k; scanf("%d %d", &n, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:204:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  204 |       scanf("%d", &a[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~
#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...