oj.uz

Submission #234670

# Submission time Handle Problem Language Result Execution time Memory
234670 2020-05-25T06:12:30 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>

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;

int solve(int n, int k){
  shuffle(v + 1, v + n + 1, rng);
  Rect base[1 + sigma];
  for(int i = 1; i <= k; i++)
    base[i] = {1, 1, inf, inf};

  for(int i = 1;i <= n; i++){
    bool found = 0;
    for(int j = 1;j <= k; j++) {
      if((base[j] + v[i]).valid()){
        found = 1;
        base[j] = base[j] + v[i];
        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) == 0);
  return 0;
}

Subtask #1
1.0 / 1.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 1 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 4 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 2 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 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 6 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct
12 Correct 3 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 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 737 ms 424 KB Output is correct
8 Correct 180 ms 420 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 817 ms 504 KB Output is correct
11 Correct 692 ms 428 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 1221 ms 504 KB Output is correct
14 Correct 203 ms 384 KB Output is correct
15 Correct 38 ms 384 KB Output is correct
16 Correct 563 ms 420 KB Output is correct
17 Correct 349 ms 384 KB Output is correct
18 Correct 227 ms 384 KB Output is correct
19 Correct 42 ms 384 KB Output is correct
20 Execution timed out 3051 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 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 1 ms 384 KB Output is correct
5 Correct 99 ms 3448 KB Output is correct
6 Correct 104 ms 3448 KB Output is correct
7 Correct 103 ms 3448 KB Output is correct
8 Correct 101 ms 3448 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 276 ms 3404 KB Output is correct
6 Execution timed out 3073 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 4 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 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 6 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 1561 ms 3520 KB Output is correct
14 Correct 2117 ms 3516 KB Output is correct
15 Correct 327 ms 3520 KB Output is correct
16 Correct 1463 ms 3516 KB Output is correct
17 Correct 192 ms 3576 KB Output is correct
18 Correct 2283 ms 3520 KB Output is correct
19 Execution timed out 3054 ms 3448 KB Time limit exceeded
20 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 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 737 ms 424 KB Output is correct
8 Correct 180 ms 420 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 817 ms 504 KB Output is correct
11 Correct 692 ms 428 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 1221 ms 504 KB Output is correct
14 Correct 203 ms 384 KB Output is correct
15 Correct 38 ms 384 KB Output is correct
16 Correct 563 ms 420 KB Output is correct
17 Correct 349 ms 384 KB Output is correct
18 Correct 227 ms 384 KB Output is correct
19 Correct 42 ms 384 KB Output is correct
20 Execution timed out 3051 ms 384 KB Time limit exceeded
21 Halted 0 ms 0 KB -