oj.uz

Submission #218224

# Submission time Handle Problem Language Result Execution time Memory
218224 2020-04-01T14:48:50 Z MiricaMatei Hamburg Steak (JOI20_hamburg) C++14
6 / 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];

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;
      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 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
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 4 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 13 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 60 ms 384 KB Output is correct
11 Correct 9 ms 384 KB Output is correct
12 Correct 20 ms 288 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 4 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 372 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 142 ms 396 KB Output is correct
8 Correct 35 ms 288 KB Output is correct
9 Correct 32 ms 384 KB Output is correct
10 Correct 168 ms 504 KB Output is correct
11 Correct 160 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 1672 ms 384 KB Output is correct
14 Correct 712 ms 384 KB Output is correct
15 Correct 267 ms 384 KB Output is correct
16 Correct 688 ms 400 KB Output is correct
17 Correct 116 ms 384 KB Output is correct
18 Correct 339 ms 400 KB Output is correct
19 Correct 23 ms 384 KB Output is correct
20 Execution timed out 3077 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 2 ms 384 KB Output is correct
5 Correct 151 ms 3488 KB Output is correct
6 Correct 145 ms 3452 KB Output is correct
7 Correct 143 ms 3448 KB Output is correct
8 Correct 146 ms 3448 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 554 ms 3496 KB Output is correct
6 Execution timed out 3032 ms 3400 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 4 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 13 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 60 ms 384 KB Output is correct
11 Correct 9 ms 384 KB Output is correct
12 Correct 20 ms 288 KB Output is correct
13 Correct 444 ms 3496 KB Output is correct
14 Correct 1918 ms 3496 KB Output is correct
15 Correct 1933 ms 3380 KB Output is correct
16 Correct 1574 ms 3492 KB Output is correct
17 Correct 1573 ms 3540 KB Output is correct
18 Correct 2179 ms 3576 KB Output is correct
19 Execution timed out 3057 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 4 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 372 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 142 ms 396 KB Output is correct
8 Correct 35 ms 288 KB Output is correct
9 Correct 32 ms 384 KB Output is correct
10 Correct 168 ms 504 KB Output is correct
11 Correct 160 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 1672 ms 384 KB Output is correct
14 Correct 712 ms 384 KB Output is correct
15 Correct 267 ms 384 KB Output is correct
16 Correct 688 ms 400 KB Output is correct
17 Correct 116 ms 384 KB Output is correct
18 Correct 339 ms 400 KB Output is correct
19 Correct 23 ms 384 KB Output is correct
20 Execution timed out 3077 ms 384 KB Time limit exceeded
21 Halted 0 ms 0 KB -