oj.uz

Submission #218222

# Submission time Handle Problem Language Result Execution time Memory
218222 2020-04-01T14:47:47 Z MiricaMatei Hamburg Steak (JOI20_hamburg) C++14
3 / 100
 3000 ms 3464 KB 
#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];

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);

  while (1) {
    for (int i = 1; i <= k; ++i)
      sol[i] = {1, 1, INF, INF};
    shuffle(v + 1, v + n + 1, rng);
    bool gas = 1;
    for (int i = 1; i <= n; ++i) {
      bool ok = 0;
      shuffle(sol + 1, sol + k + 1, rng);
      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;
          break;
        }
      }
      if (!ok) {
        gas = 0;
        break;
      }
    }
    if (gas) {
      for (int i = 1; i <= k; ++i)
        printf("%d %d\n", sol[i].x1, sol[i].y1);
      return 0;
    }
  }

  return 0;
}

Compilation message

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 26 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 5 ms 384 KB Output is correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 396 KB Output is correct
2 Execution timed out 3089 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 384 KB Output is correct
2 Correct 359 ms 384 KB Output is correct
3 Correct 246 ms 384 KB Output is correct
4 Execution timed out 3024 ms 384 KB Time limit exceeded
5 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 3 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 144 ms 3424 KB Output is correct
6 Correct 158 ms 3448 KB Output is correct
7 Correct 150 ms 3448 KB Output is correct
8 Correct 174 ms 3464 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 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 5 ms 384 KB Output is correct
5 Execution timed out 3096 ms 3448 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 396 KB Output is correct
2 Execution timed out 3089 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 384 KB Output is correct
2 Correct 359 ms 384 KB Output is correct
3 Correct 246 ms 384 KB Output is correct
4 Execution timed out 3024 ms 384 KB Time limit exceeded
5 Halted 0 ms 0 KB -