Submission #218231

#	Time	Username	Problem	Language	Result	Execution time	Memory
218231		MiricaMatei	Hamburg Steak (JOI20_hamburg)	C++14	2 / 100	3088 ms	3576 KiB

hamburg

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;
const int MAXK = 4;
const int INF = 1000000000;

struct Drept {
  int x1, y1, x2, y2;
} v[MAXN], sol[MAXK + 5], sol1[MAXK + 5], sol2[MAXK + 5];

pair<bool, Drept> inters(const Drept& a, const Drept& b) {
  Drept c;
  c.x1 = max(a.x1, b.x1);
  c.y1 = max(a.y1, b.y1);
  c.x2 = min(a.x2, b.x2);
  c.y2 = min(a.y2, b.y2);
  if (c.x1 <= c.x2 && c.y1 <= c.y2)
    return {1, c};
  return {0, c};
}

int main() {
  //freopen("date.in", "r", stdin);
  //freopen("date.out", "w", stdout);

  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i)
    scanf("%d%d%d%d", &v[i].x1, &v[i].y1, &v[i].x2, &v[i].y2);

  shuffle(v + 1, v + n + 1, rng);
  while (1) {
    for (int i = 1; i <= k; ++i)
      sol[i] = {1, 1, INF, INF};
    bool gas = 1;
    int m = 0, t = 0;
    for (int i = 1; i <= n; ++i) {
      bool ok = 0;
      for (int j = 1; j <= k; ++j) {
        pair<bool, Drept>aux = inters(sol[j], v[i]);
        if (aux.first) {
          swap(sol[j], aux.second);
          ok = 1;
          sol2[++t] = v[i];
          break;
        }
      }
      if (!ok) {
        gas = 0;
        sol1[++m] = v[i];
      }
    }
    if (gas) {
      for (int i = 1; i <= k; ++i)
        printf("%d %d\n", sol[i].x1, sol[i].y1);
      return 0;
    }
    shuffle(sol1 + 1, sol1 + m + 1, rng);
    for (int i = 1; i <= m; ++i)
      sol[i] = sol1[i];
    for (int i = 1; i <= t; ++i)
      sol[m + i] = sol2[i];
  }

  return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     scanf("%d%d%d%d", &v[i].x1, &v[i].y1, &v[i].x2, &v[i].y2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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