Submission #652816

#	Time	Username	Problem	Language	Result	Execution time	Memory
652816		XCAC197	함박 스테이크 (JOI20_hamburg)	C++14	21 / 100	3098 ms	15908 KiB

hamburg

//This code is meant to test lunchbox's code against the stronger test data. All credit is due to lunchbox (Dong Liu)
/*
 author: lunchbox
 problem link: https://c...content-available-to-author-only...s.com/group/uodset6U2h/contest/405473/problem/C
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5, MX = 1e9;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct rect {
 long long l, d, u, r, i;

 rect operator+(const rect& o) {
  return {max(l, o.l), max(d, o.d), min(u, o.u), min(r, o.r), -1};
 }
 bool empty() const {
  return l > r || d > u;
 }
 long long area() const {
  assert(!empty());
  return 1LL * (r - l + 1) * (u - d + 1);
 }
} a[N];

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int n, k; cin >> n >> k;
 for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].d >> a[i].r >> a[i].u, a[i].i = i;
 if (k >= n) {
  for (int i = 0; i < n; i++) cout << a[i].l << ' ' << a[i].d << '\n';
  for (int i = n; i < k; i++) cout << 1 << ' ' << 1 << '\n';
  return 0;
 }
 while (1) {
  static rect b[4];
  for (int i = 0; i < n; i++) swap(a[i], a[rng() % (i + 1)]);
  for (int i = 0; i < k; i++) b[i] = a[i];
  bool g = 1;
  for (int i = k; i < n; i++) {
   int u = -1;
   for (int j = 0; j < k; j++)
    if (!(b[j] + a[i]).empty() && (u == -1 || (__int128) (b[j] + a[i]).area() * b[u].area() > (__int128) (b[u] + a[i]).area() * b[j].area()))
     u = j;
   if (u == -1) {
    g = 0;
    break;
   } else
    b[u] = b[u] + a[i];
  }
  if (g) {
   for (int i = 0; i < k; i++) cout << b[i].l << ' ' << b[i].d << '\n';
   break;
  }
 }
 return 0;
}//

• 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