Submission #212542

#	Time	Username	Problem	Language	Result	Execution time	Memory
212542		eriksuenderhauf	Hamburg Steak (JOI20_hamburg)	C++11	21 / 100	874 ms	16904 KiB

hamburg

//#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]);
      |       ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79