답안 #49848 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49848	2018-06-03T19:34:39 Z	zemen	원 고르기 (APIO18_circle_selection)	C++17	87 / 100	3000 ms	58248 KB

circle_selection

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int inf = 2e9 + 5;

struct Circle {
  int x, y, r, id, ord;

  static ll sqr(ll x) {
    return x * x;
  }

  bool intersects(const Circle& c) const {
    return sqr(c.x - x) + sqr(c.y - y) <= sqr(r + c.r);
  }
};
istream& operator>>(istream& in, Circle& c) {
  return in >> c.x >> c.y >> c.r;
}

struct Bbox {
  int xl, xr, yl, yr;

  Bbox() : xl(inf), xr(-inf), yl(inf), yr(-inf) {
  }

  void add(const Circle& c) {
    xl = min<ll>(xl, c.x - c.r);
    xr = max<ll>(xr, c.x + c.r);
    yl = min<ll>(yl, c.y - c.r);
    yr = max<ll>(yr, c.y + c.r);
  }

  bool intersects(const Circle& c) const {
    if (empty()) {
      return false;
    }
    if (c.x - c.r > xr || c.x + c.r < xl) {
      return false;
    }
    if (c.y - c.r > yr || c.y + c.r < yl) {
      return false;
    }
    return true;
  }

  bool empty() const {
    return xl == inf;
  }
};

const int base = 1 << 19;
Bbox box[base * 2];
Circle cleaf[base * 2];
bool leaf[base * 2];
int endv[base];

bool cmpx(const Circle& a, const Circle& b) {
  return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool cmpy(const Circle& a, const Circle& b) {
  return a.y < b.y || (a.y == b.y && a.x < b.x);
}

bool cmpr(const Circle& a, const Circle& b) {
  return a.r > b.r || (a.r == b.r && a.id < b.id);
}

void build(int v, vector<Circle> t, bool byx) {
  assert(!t.empty());
  sort(t.begin(), t.end(), byx ? cmpx : cmpy);
  if (t.size() == 1) {
    endv[t[0].id] = v;
    leaf[v] = true;
    cleaf[v] = t[0];
    return;
  }
  int n = (int) t.size();
  vector<Circle> t2(t.begin() + n / 2, t.end());
  t.resize(n / 2);
  build(v * 2, t, !byx);
  build(v * 2 + 1, t2, !byx);
}

int lookup(const Circle& c, int v = 1) {
  if (!box[v].intersects(c)) {
    return inf;
  }
  if (leaf[v]) {
    if (cleaf[v].intersects(c)) {
      return cleaf[v].ord;
    } else {
      return inf;
    }
  }
  return min(lookup(c, v * 2), lookup(c, v * 2 + 1));
}

void turn_on(const Circle& c) {
  int v = endv[c.id];
  while (v >= 1) {
    box[v].add(c);
    v /= 2;
  }
}

signed main() {
#ifdef LOCAL
  assert(freopen("b.in", "r", stdin));
#endif
  int n;
  cin >> n;
  vector<Circle> cs;
  for (int i = 0; i < n; ++i) {
    Circle c;
    cin >> c;
    c.id = i;
    cs.push_back(c);
  }
  sort(cs.begin(), cs.end(), cmpr);
  for (int i = 0; i < (int) cs.size(); ++i) {
    cs[i].ord = i;
  }
  build(1, cs, true);

  vector<int> res(n);
  for (auto& c : cs) {
    int id = lookup(c);
    if (id == inf) {
      turn_on(c);
      id = c.id;
    } else {
      id = cs[id].id;
    }
    res[c.id] = id;
  }
  for (int x : res) {
    cout << x + 1 << ' ';
  }
  cout << '\n';
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	16760 KB	Output is correct
2	Correct	16 ms	16760 KB	Output is correct
3	Correct	16 ms	16820 KB	Output is correct
4	Correct	19 ms	16876 KB	Output is correct
5	Correct	16 ms	16928 KB	Output is correct
6	Correct	14 ms	16928 KB	Output is correct
7	Correct	21 ms	16928 KB	Output is correct
8	Correct	19 ms	16928 KB	Output is correct
9	Correct	15 ms	16996 KB	Output is correct
10	Correct	15 ms	16996 KB	Output is correct
11	Correct	14 ms	16996 KB	Output is correct
12	Correct	16 ms	16996 KB	Output is correct
13	Correct	15 ms	16996 KB	Output is correct
14	Correct	14 ms	16996 KB	Output is correct
15	Correct	14 ms	17000 KB	Output is correct
16	Correct	16 ms	17260 KB	Output is correct
17	Correct	20 ms	17260 KB	Output is correct
18	Correct	20 ms	17260 KB	Output is correct
19	Correct	31 ms	17612 KB	Output is correct
20	Correct	27 ms	17612 KB	Output is correct
21	Correct	30 ms	17628 KB	Output is correct
22	Correct	30 ms	17736 KB	Output is correct
23	Correct	32 ms	17736 KB	Output is correct
24	Correct	31 ms	17736 KB	Output is correct
25	Correct	31 ms	17736 KB	Output is correct
26	Correct	27 ms	17748 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	883 ms	57840 KB	Output is correct
2	Correct	860 ms	58148 KB	Output is correct
3	Correct	863 ms	58148 KB	Output is correct
4	Correct	969 ms	58148 KB	Output is correct
5	Correct	980 ms	58148 KB	Output is correct
6	Correct	1088 ms	58148 KB	Output is correct
7	Correct	1123 ms	58148 KB	Output is correct
8	Correct	1091 ms	58148 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	58148 KB	Output is correct
2	Correct	419 ms	58148 KB	Output is correct
3	Correct	1480 ms	58148 KB	Output is correct
4	Correct	1403 ms	58148 KB	Output is correct
5	Correct	1398 ms	58148 KB	Output is correct
6	Correct	708 ms	58148 KB	Output is correct
7	Correct	336 ms	58148 KB	Output is correct
8	Correct	71 ms	58148 KB	Output is correct
9	Correct	1423 ms	58148 KB	Output is correct
10	Correct	1651 ms	58148 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1434 ms	58212 KB	Output is correct
2	Correct	1269 ms	58212 KB	Output is correct
3	Correct	1618 ms	58212 KB	Output is correct
4	Correct	1404 ms	58212 KB	Output is correct
5	Correct	1329 ms	58212 KB	Output is correct
6	Correct	1484 ms	58212 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	16760 KB	Output is correct
2	Correct	16 ms	16760 KB	Output is correct
3	Correct	16 ms	16820 KB	Output is correct
4	Correct	19 ms	16876 KB	Output is correct
5	Correct	16 ms	16928 KB	Output is correct
6	Correct	14 ms	16928 KB	Output is correct
7	Correct	21 ms	16928 KB	Output is correct
8	Correct	19 ms	16928 KB	Output is correct
9	Correct	15 ms	16996 KB	Output is correct
10	Correct	15 ms	16996 KB	Output is correct
11	Correct	14 ms	16996 KB	Output is correct
12	Correct	16 ms	16996 KB	Output is correct
13	Correct	15 ms	16996 KB	Output is correct
14	Correct	14 ms	16996 KB	Output is correct
15	Correct	14 ms	17000 KB	Output is correct
16	Correct	16 ms	17260 KB	Output is correct
17	Correct	20 ms	17260 KB	Output is correct
18	Correct	20 ms	17260 KB	Output is correct
19	Correct	31 ms	17612 KB	Output is correct
20	Correct	27 ms	17612 KB	Output is correct
21	Correct	30 ms	17628 KB	Output is correct
22	Correct	30 ms	17736 KB	Output is correct
23	Correct	32 ms	17736 KB	Output is correct
24	Correct	31 ms	17736 KB	Output is correct
25	Correct	31 ms	17736 KB	Output is correct
26	Correct	27 ms	17748 KB	Output is correct
27	Correct	49 ms	58212 KB	Output is correct
28	Correct	46 ms	58212 KB	Output is correct
29	Correct	48 ms	58212 KB	Output is correct
30	Correct	154 ms	58212 KB	Output is correct
31	Correct	48 ms	58212 KB	Output is correct
32	Correct	43 ms	58212 KB	Output is correct
33	Correct	358 ms	58212 KB	Output is correct
34	Correct	355 ms	58212 KB	Output is correct
35	Correct	363 ms	58212 KB	Output is correct
36	Correct	371 ms	58212 KB	Output is correct
37	Correct	365 ms	58212 KB	Output is correct
38	Correct	372 ms	58212 KB	Output is correct
39	Correct	436 ms	58212 KB	Output is correct
40	Correct	491 ms	58212 KB	Output is correct
41	Correct	531 ms	58212 KB	Output is correct
42	Correct	402 ms	58212 KB	Output is correct
43	Correct	359 ms	58212 KB	Output is correct
44	Correct	353 ms	58212 KB	Output is correct
45	Correct	343 ms	58212 KB	Output is correct
46	Correct	337 ms	58212 KB	Output is correct
47	Correct	382 ms	58212 KB	Output is correct
48	Correct	345 ms	58212 KB	Output is correct
49	Correct	370 ms	58212 KB	Output is correct
50	Correct	320 ms	58212 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	16760 KB	Output is correct
2	Correct	16 ms	16760 KB	Output is correct
3	Correct	16 ms	16820 KB	Output is correct
4	Correct	19 ms	16876 KB	Output is correct
5	Correct	16 ms	16928 KB	Output is correct
6	Correct	14 ms	16928 KB	Output is correct
7	Correct	21 ms	16928 KB	Output is correct
8	Correct	19 ms	16928 KB	Output is correct
9	Correct	15 ms	16996 KB	Output is correct
10	Correct	15 ms	16996 KB	Output is correct
11	Correct	14 ms	16996 KB	Output is correct
12	Correct	16 ms	16996 KB	Output is correct
13	Correct	15 ms	16996 KB	Output is correct
14	Correct	14 ms	16996 KB	Output is correct
15	Correct	14 ms	17000 KB	Output is correct
16	Correct	16 ms	17260 KB	Output is correct
17	Correct	20 ms	17260 KB	Output is correct
18	Correct	20 ms	17260 KB	Output is correct
19	Correct	31 ms	17612 KB	Output is correct
20	Correct	27 ms	17612 KB	Output is correct
21	Correct	30 ms	17628 KB	Output is correct
22	Correct	30 ms	17736 KB	Output is correct
23	Correct	32 ms	17736 KB	Output is correct
24	Correct	31 ms	17736 KB	Output is correct
25	Correct	31 ms	17736 KB	Output is correct
26	Correct	27 ms	17748 KB	Output is correct
27	Correct	883 ms	57840 KB	Output is correct
28	Correct	860 ms	58148 KB	Output is correct
29	Correct	863 ms	58148 KB	Output is correct
30	Correct	969 ms	58148 KB	Output is correct
31	Correct	980 ms	58148 KB	Output is correct
32	Correct	1088 ms	58148 KB	Output is correct
33	Correct	1123 ms	58148 KB	Output is correct
34	Correct	1091 ms	58148 KB	Output is correct
35	Correct	14 ms	58148 KB	Output is correct
36	Correct	419 ms	58148 KB	Output is correct
37	Correct	1480 ms	58148 KB	Output is correct
38	Correct	1403 ms	58148 KB	Output is correct
39	Correct	1398 ms	58148 KB	Output is correct
40	Correct	708 ms	58148 KB	Output is correct
41	Correct	336 ms	58148 KB	Output is correct
42	Correct	71 ms	58148 KB	Output is correct
43	Correct	1423 ms	58148 KB	Output is correct
44	Correct	1651 ms	58148 KB	Output is correct
45	Correct	1434 ms	58212 KB	Output is correct
46	Correct	1269 ms	58212 KB	Output is correct
47	Correct	1618 ms	58212 KB	Output is correct
48	Correct	1404 ms	58212 KB	Output is correct
49	Correct	1329 ms	58212 KB	Output is correct
50	Correct	1484 ms	58212 KB	Output is correct
51	Correct	49 ms	58212 KB	Output is correct
52	Correct	46 ms	58212 KB	Output is correct
53	Correct	48 ms	58212 KB	Output is correct
54	Correct	154 ms	58212 KB	Output is correct
55	Correct	48 ms	58212 KB	Output is correct
56	Correct	43 ms	58212 KB	Output is correct
57	Correct	358 ms	58212 KB	Output is correct
58	Correct	355 ms	58212 KB	Output is correct
59	Correct	363 ms	58212 KB	Output is correct
60	Correct	371 ms	58212 KB	Output is correct
61	Correct	365 ms	58212 KB	Output is correct
62	Correct	372 ms	58212 KB	Output is correct
63	Correct	436 ms	58212 KB	Output is correct
64	Correct	491 ms	58212 KB	Output is correct
65	Correct	531 ms	58212 KB	Output is correct
66	Correct	402 ms	58212 KB	Output is correct
67	Correct	359 ms	58212 KB	Output is correct
68	Correct	353 ms	58212 KB	Output is correct
69	Correct	343 ms	58212 KB	Output is correct
70	Correct	337 ms	58212 KB	Output is correct
71	Correct	382 ms	58212 KB	Output is correct
72	Correct	345 ms	58212 KB	Output is correct
73	Correct	370 ms	58212 KB	Output is correct
74	Correct	320 ms	58212 KB	Output is correct
75	Correct	1321 ms	58212 KB	Output is correct
76	Correct	1521 ms	58212 KB	Output is correct
77	Correct	1131 ms	58212 KB	Output is correct
78	Correct	1128 ms	58212 KB	Output is correct
79	Correct	1291 ms	58212 KB	Output is correct
80	Correct	1293 ms	58212 KB	Output is correct
81	Correct	1236 ms	58212 KB	Output is correct
82	Correct	1234 ms	58212 KB	Output is correct
83	Correct	1199 ms	58212 KB	Output is correct
84	Correct	1392 ms	58212 KB	Output is correct
85	Correct	1346 ms	58212 KB	Output is correct
86	Correct	1399 ms	58248 KB	Output is correct
87	Correct	1396 ms	58248 KB	Output is correct
88	Correct	1710 ms	58248 KB	Output is correct
89	Correct	1827 ms	58248 KB	Output is correct
90	Correct	1760 ms	58248 KB	Output is correct
91	Correct	1707 ms	58248 KB	Output is correct
92	Correct	1549 ms	58248 KB	Output is correct
93	Correct	1528 ms	58248 KB	Output is correct
94	Execution timed out	3039 ms	58248 KB	Time limit exceeded
95	Halted	0 ms	0 KB	-

답안 #49848

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 13.0