oj.uz

Submission #218231

# Submission time Handle Problem Language Result Execution time Memory
218231 2020-04-01T15:07:45 Z MiricaMatei Hamburg Steak (JOI20_hamburg) C++14
2 / 100
 3000 ms 3576 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], sol1[MAXK + 5], sol2[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);

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

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

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 384 KB Time limit exceeded
2 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 2 ms 384 KB Output is correct
5 Correct 148 ms 3448 KB Output is correct
6 Correct 145 ms 3448 KB Output is correct
7 Correct 143 ms 3448 KB Output is correct
8 Correct 157 ms 3576 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -