Submission #234673

#	Time	Username	Problem	Language	Result	Execution time	Memory
234673		AlexLuchianov	Hamburg Steak (JOI20_hamburg)	C++14	6 / 100	3066 ms	3576 KiB

hamburg

#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
#include <random>
#include <algorithm>
#include <chrono>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int const inf = 1000000000;

int const sigma = 4;

class Rect{
public:
  int x;
  int y;
  int x2;
  int y2;
  Rect operator + (Rect a) {
    return {max(x, a.x), max(y, a.y), min(x2, a.x2), min(y2, a.y2)};
  }
  bool valid(){
    return (x <= x2) && (y <= y2);
  }
  ll area(){
    return 1LL * (x2 - x + 1) * (y2 - y + 1);
  }
} v[1 + nmax];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int solve(int n, int k, int mode){
  shuffle(v + 1, v + n + 1, rng);
  Rect base[1 + sigma];
  for(int i = 1; i <= k; i++)
    base[i] = {1, 1, inf, inf};
  if(mode == 1){
    for(int i = 1;i <= n; i++){
      ll smin = 1LL * inf * inf;
      for(int j = 1;j <= k; j++) {
        Rect newp = base[j] + v[i];
        if(newp.valid())
          smin = min(smin, base[j].area() - newp.area());
      }

      if(smin == 1LL * inf * inf)
        return 0;

      for(int j = 1;j <= k; j++) {
        Rect newp = base[j] + v[i];
        if(newp.valid() && base[j].area() - newp.area() == smin) {
           base[j] = newp;
           break;
        }
      }
    }
  } else {
    for(int i = 1;i <= n; i++) {
      bool found = 0;
      for(int j = 1;j <= k; j++){
        Rect newp = base[j] + v[i];
        if(newp.valid()) {
          base[j] = newp;
          found = 1;
          break;
        }
      }
      if(found == 0)
        return 0;
    }
  }

  for(int j = 1;j <= k; j++)
    cout << base[j].x << " " << base[j].y << '\n';
  return 1;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  cin >> n >> k;
  for(int i = 1;i <= n; i++)
    cin >> v[i].x >> v[i].y >> v[i].x2 >> v[i].y2;
  while(solve(n, k, 2) == 0);
  return 0;
}

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