oj.uz

Submission #212542

# Submission time Handle Problem Language Result Execution time Memory
212542 2020-03-23T12:32:56 Z eriksuenderhauf Hamburg Steak (JOI20_hamburg) C++11
21 / 100
 874 ms 16904 KB 
//#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 4 ms 512 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 5 ms 528 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 4 ms 512 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 3 ms 512 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 4 ms 384 KB Output is correct
33 Correct 4 ms 384 KB Output is correct
34 Correct 4 ms 512 KB Output is correct
35 Correct 4 ms 512 KB Output is correct
36 Correct 4 ms 512 KB Output is correct
37 Correct 6 ms 512 KB Output is correct
38 Correct 6 ms 512 KB Output is correct
39 Correct 6 ms 512 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 5 ms 512 KB Output is correct
42 Correct 5 ms 512 KB Output is correct
43 Correct 11 ms 512 KB Output is correct
44 Correct 4 ms 512 KB Output is correct
45 Correct 4 ms 384 KB Output is correct
46 Correct 6 ms 512 KB Output is correct
47 Correct 6 ms 512 KB Output is correct
48 Correct 10 ms 512 KB Output is correct
49 Correct 4 ms 512 KB Output is correct
50 Correct 5 ms 512 KB Output is correct
51 Correct 5 ms 512 KB Output is correct
52 Correct 4 ms 512 KB Output is correct
53 Correct 4 ms 512 KB Output is correct
54 Correct 5 ms 512 KB Output is correct
55 Correct 4 ms 384 KB Output is correct
56 Correct 4 ms 384 KB Output is correct
57 Correct 4 ms 384 KB Output is correct
58 Correct 4 ms 384 KB Output is correct

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 163 ms 3456 KB Output is correct
6 Correct 160 ms 3508 KB Output is correct
7 Correct 174 ms 3512 KB Output is correct
8 Correct 160 ms 3508 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 164 ms 5616 KB Output is correct
6 Correct 171 ms 5596 KB Output is correct
7 Correct 165 ms 5612 KB Output is correct
8 Correct 195 ms 7656 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 183 ms 7140 KB Output is correct
14 Correct 189 ms 7388 KB Output is correct
15 Correct 199 ms 7504 KB Output is correct
16 Correct 173 ms 6556 KB Output is correct
17 Correct 231 ms 7404 KB Output is correct
18 Correct 180 ms 5520 KB Output is correct
19 Correct 233 ms 9872 KB Output is correct
20 Correct 191 ms 10156 KB Output is correct
21 Correct 266 ms 13708 KB Output is correct
22 Correct 202 ms 9628 KB Output is correct
23 Correct 221 ms 12180 KB Output is correct
24 Correct 214 ms 13364 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 4 ms 512 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 5 ms 528 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 4 ms 512 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 3 ms 512 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 4 ms 384 KB Output is correct
33 Correct 4 ms 384 KB Output is correct
34 Correct 4 ms 512 KB Output is correct
35 Correct 4 ms 512 KB Output is correct
36 Correct 4 ms 512 KB Output is correct
37 Correct 6 ms 512 KB Output is correct
38 Correct 6 ms 512 KB Output is correct
39 Correct 6 ms 512 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 5 ms 512 KB Output is correct
42 Correct 5 ms 512 KB Output is correct
43 Correct 11 ms 512 KB Output is correct
44 Correct 4 ms 512 KB Output is correct
45 Correct 4 ms 384 KB Output is correct
46 Correct 6 ms 512 KB Output is correct
47 Correct 6 ms 512 KB Output is correct
48 Correct 10 ms 512 KB Output is correct
49 Correct 4 ms 512 KB Output is correct
50 Correct 5 ms 512 KB Output is correct
51 Correct 5 ms 512 KB Output is correct
52 Correct 4 ms 512 KB Output is correct
53 Correct 4 ms 512 KB Output is correct
54 Correct 5 ms 512 KB Output is correct
55 Correct 4 ms 384 KB Output is correct
56 Correct 4 ms 384 KB Output is correct
57 Correct 4 ms 384 KB Output is correct
58 Correct 4 ms 384 KB Output is correct
59 Correct 247 ms 9840 KB Output is correct
60 Correct 225 ms 8572 KB Output is correct
61 Correct 233 ms 9724 KB Output is correct
62 Correct 202 ms 8112 KB Output is correct
63 Correct 249 ms 9672 KB Output is correct
64 Correct 192 ms 5444 KB Output is correct
65 Correct 236 ms 13204 KB Output is correct
66 Correct 251 ms 12136 KB Output is correct
67 Correct 278 ms 13424 KB Output is correct
68 Correct 266 ms 12728 KB Output is correct
69 Correct 260 ms 13744 KB Output is correct
70 Correct 260 ms 12656 KB Output is correct
71 Correct 471 ms 16728 KB Output is correct
72 Correct 455 ms 15996 KB Output is correct
73 Correct 403 ms 15864 KB Output is correct
74 Correct 372 ms 16632 KB Output is correct
75 Correct 370 ms 14460 KB Output is correct
76 Correct 339 ms 14904 KB Output is correct
77 Correct 376 ms 15564 KB Output is correct
78 Correct 523 ms 15948 KB Output is correct
79 Correct 410 ms 14680 KB Output is correct
80 Correct 385 ms 15984 KB Output is correct
81 Correct 447 ms 15300 KB Output is correct
82 Correct 336 ms 14256 KB Output is correct
83 Correct 310 ms 15816 KB Output is correct
84 Correct 293 ms 13408 KB Output is correct
85 Correct 359 ms 16356 KB Output is correct
86 Correct 281 ms 14144 KB Output is correct
87 Correct 333 ms 16312 KB Output is correct
88 Correct 332 ms 16012 KB Output is correct
89 Correct 406 ms 15032 KB Output is correct
90 Correct 530 ms 15900 KB Output is correct
91 Correct 408 ms 14044 KB Output is correct
92 Correct 506 ms 16904 KB Output is correct
93 Correct 442 ms 16292 KB Output is correct
94 Correct 503 ms 15660 KB Output is correct
95 Correct 529 ms 16200 KB Output is correct
96 Correct 583 ms 15944 KB Output is correct
97 Correct 497 ms 15816 KB Output is correct
98 Correct 414 ms 15168 KB Output is correct
99 Correct 430 ms 15836 KB Output is correct
100 Correct 501 ms 15924 KB Output is correct
101 Correct 468 ms 15960 KB Output is correct
102 Correct 460 ms 11268 KB Output is correct
103 Correct 563 ms 16456 KB Output is correct
104 Correct 472 ms 14636 KB Output is correct
105 Correct 524 ms 16448 KB Output is correct
106 Correct 457 ms 16088 KB Output is correct
107 Correct 462 ms 16228 KB Output is correct
108 Correct 474 ms 16084 KB Output is correct
109 Correct 510 ms 15840 KB Output is correct
110 Correct 492 ms 16348 KB Output is correct
111 Correct 492 ms 14888 KB Output is correct
112 Correct 519 ms 16556 KB Output is correct
113 Correct 379 ms 11572 KB Output is correct
114 Correct 385 ms 11600 KB Output is correct
115 Correct 398 ms 11640 KB Output is correct
116 Correct 399 ms 11656 KB Output is correct
117 Incorrect 874 ms 15600 KB Unexpected end of file - int32 expected
118 Halted 0 ms 0 KB -