oj.uz

Submission #234673

# Submission time Handle Problem Language Result Execution time Memory
234673 2020-05-25T06:23:40 Z AlexLuchianov Hamburg Steak (JOI20_hamburg) C++14
6 / 100
 3000 ms 3576 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 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 6 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 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 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 3 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 9 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 35 ms 428 KB Output is correct
11 Correct 18 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 7 ms 432 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 395 ms 384 KB Output is correct
8 Correct 102 ms 424 KB Output is correct
9 Correct 25 ms 384 KB Output is correct
10 Correct 56 ms 420 KB Output is correct
11 Correct 85 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 743 ms 424 KB Output is correct
14 Correct 516 ms 424 KB Output is correct
15 Correct 118 ms 384 KB Output is correct
16 Correct 167 ms 504 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 15 ms 384 KB Output is correct
19 Correct 251 ms 504 KB Output is correct
20 Execution timed out 3055 ms 384 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 105 ms 3448 KB Output is correct
6 Correct 96 ms 3448 KB Output is correct
7 Correct 114 ms 3452 KB Output is correct
8 Correct 97 ms 3448 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 141 ms 3520 KB Output is correct
6 Execution timed out 3054 ms 3448 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 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 9 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 35 ms 428 KB Output is correct
11 Correct 18 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 1084 ms 3532 KB Output is correct
14 Correct 1419 ms 3516 KB Output is correct
15 Correct 2103 ms 3576 KB Output is correct
16 Execution timed out 3066 ms 3396 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 7 ms 432 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 395 ms 384 KB Output is correct
8 Correct 102 ms 424 KB Output is correct
9 Correct 25 ms 384 KB Output is correct
10 Correct 56 ms 420 KB Output is correct
11 Correct 85 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 743 ms 424 KB Output is correct
14 Correct 516 ms 424 KB Output is correct
15 Correct 118 ms 384 KB Output is correct
16 Correct 167 ms 504 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 15 ms 384 KB Output is correct
19 Correct 251 ms 504 KB Output is correct
20 Execution timed out 3055 ms 384 KB Time limit exceeded
21 Halted 0 ms 0 KB -