답안 #48955 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48955	2018-05-20T10:18:27 Z	azneye	원 고르기 (APIO18_circle_selection)	C++17	87 / 100	3000 ms	761472 KB

circle_selection

#include <bits/stdc++.h>

using namespace std;

namespace {

const unsigned int buffer_size = 1 << 16;
char input_buffer[buffer_size + 1];
unsigned int bytes_read = 0;
unsigned int input_index = 0;

inline char next_char() {
  if (input_index == bytes_read) {
    bytes_read = fread(input_buffer, sizeof(char), buffer_size, stdin);
    input_buffer[bytes_read] = '\0'; //sentinel
    input_index = 0;
  }
  return input_buffer[input_index++];
}

inline int next_int() {
  char c = 0;
  int ans = 0;
  while (c < '-')
    c = next_char();
  bool neg = false;
  if (c == '-') {
    neg = true;
    c = next_char();
  }
  for (; c >= '0'; c = next_char())
    ans = (ans << 1) + (ans << 3) + c - '0';
  return neg ? -ans : ans;
}

inline void next_str(char* str) {
  char c = next_char();
  while (c > ' ') {
    *str++ = c;
    c = next_char();
  }
  *str = '\0';
}

char output_buffer[buffer_size];
unsigned int output_index = 0;

inline void write_flush() {
  fwrite(output_buffer, sizeof(char), output_index, stdout);
  output_index = 0;
}

inline void write_char(char c) {
  output_buffer[output_index++] = c;
  if (output_index == buffer_size)
    write_flush();
}

inline void write_int(int num) {
  if (num >= 10)
    write_int(num / 10);
  write_char(num % 10 + '0');
}

/**
 * Currently this design only allows one arena per arena size
 *
 * @tparam SIZE size of arena in bytes, default is 200 MB
 */
template <size_t SIZE = 500 << 20> class Arena {
  static char buf[];
  static size_t buf_ind;

 public:
  template <class T> struct Allocator {
    typedef T value_type;

    Allocator() {}

    template <class U> Allocator(const U&) {}

    T* allocate(size_t n) {
      buf_ind -= n * sizeof(T);
      buf_ind &= 0 - alignof(T);
      return (T*) (buf + buf_ind);
    }

    void deallocate(T*, size_t) {}
  };

  /**
   * Frees the arena, be very sure no allocation is still used when calling this
   */
  static void Clear() {
    buf_ind = SIZE;
  }
};

template <size_t SIZE> char Arena<SIZE>::buf[SIZE];
template <size_t SIZE> size_t Arena<SIZE>::buf_ind = SIZE;


#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define DYDY(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define RARA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef int64_t ll;
typedef double dd;

ll Sq(ll x) {
  return x * x;
}

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

  bool operator<(const Circle& c) const {
    return make_pair(-r, id) < make_pair(-c.r, c.id);
  }

  bool Contains(int p, int q) const {
    return Sq(p - x) + Sq(q - y) <= Sq(r);
  }

  bool Intersects(const Circle& c) const {
    return Sq(x - c.x) + Sq(y - c.y) <= Sq(r + c.r);
  }

  bool Contains(int x1, int y1, int x2, int y2) const {
    return Contains(x1, y1) and Contains(x1, y2) and Contains(x2, y1) and Contains(x2, y2);
  }

  static bool In(int a, int b, int q) {
    // is q in [a,b]
    return a <= q and q <= b;
  }

  // does this circle intersect square
  // check if an edge intersects
  // or if circle is in square
  bool Intersects(int x1, int y1, int x2, int y2) const {
    return
      // horizontal edge intersects
      (y1 <= y + r and y - r <= y2 and (In(x - r, x + r, x1) or In(x - r, x + r, x2)))
      // vertical edge intersects
      or (x1 <= x + r and x - r <= x2 and (In(y - r, y + r, y1) or In(y - r, y + r, y2)))
      // circle is in square
      or (In(x1, x2, x) and In(y1, y2, y));
  }
};

struct Node {
  static Node pool[];
  static int next_node;
  int quad[4];
  int x1, x2, y1, y2;
  vector<int> ids; // sorted by largest radius first

  Node() {}

  Node(int x1, int y1, int x2, int y2) : x1(x1), x2(x2), y1(y1), y2(y2) {
    memset(quad, 0, sizeof(quad));
  }

  static int Alloc(int x1, int y1, int x2, int y2) {
//    return new(allocator.allocate(1)) Node(x1, x2, y1, y2);
    new(pool + next_node) Node(x1, y1, x2, y2);
    return next_node++;
  }

  void Insert(const vector<Circle>& circs) {
    if (x1 + 1 == x2 or SIZE(circs) <= 500) {
//      DEBUG(x1, y1, x2, y2);
//      RARA(c, circs) DEBUG(c.id);
      RARA(c, circs) {
        ids.push_back(c.id);
//        nodes[c.id].push_back(this);
      }
      return;
    }
    const int xm = (x1 + x2) / 2;
    const int ym = (y1 + y2) / 2;
    vector<Circle> ccs[4];
    RARA(c, circs) {
      if (c.Contains(x1, y1, x2, y2)) {
//        DEBUG(x1, y1, x2, y2, c.id);
        ids.push_back(c.id);
//        nodes[c.id].push_back(this);
        continue;
      }
      if (c.Intersects(xm, ym, x2, y2))
        ccs[0].push_back(c);
      if (c.Intersects(x1, ym, xm, y2))
        ccs[1].push_back(c);
      if (c.Intersects(x1, y1, xm, ym))
        ccs[2].push_back(c);
      if (c.Intersects(xm, y1, x2, ym))
        ccs[3].push_back(c);
    }
    VEVE(i, 0, 4) if (not ccs[i].empty()) {
        if (not quad[i]) {
          quad[i] = Alloc(i == 1 or i == 2 ? x1 : xm,
                          i >= 2 ? y1 : ym,
                          i == 1 or i == 2 ? xm : x2,
                          i >= 2 ? ym : y2);
        }
        pool[quad[i]].Insert(ccs[i]);
      }
  }

  void Erase(const Circle& c, const vector<Circle>& circs, vector<int>& res) {
    static vector<int> temp;
//    if (x1 + 1 == x2 or c.Contains(x1, y1, x2, y2)) {
//      DEBUG(c.x, c.y, c.r, x1, y1, x2, y2, ids);
    temp.clear();
    RARA(id, ids) {
      if (res[id] != -(SIZE(circs) + 1)) {
      } else if (c.Intersects(circs[id])) {
        res[id] = c.id;
      } else {
        temp.push_back(id);
      }
    }
    ids.swap(temp);
//    }
    RARA(qq, quad) {
      Node* q = pool + qq;
      if (qq and c.Intersects(q->x1, q->y1, q->x2, q->y2)) {
        q->Erase(c, circs, res);
      }
    }
  }
};

Node Node::pool[12000000];
int Node::next_node = 1;

void Solve(ll) {
//  DEBUG(sizeof(Node::pool));
  int n;
  n = next_int();
//  cin >> n;
  vector<Circle> circs(n);
  vector<int> res(n, -(n + 1));
  {
    map<tuple<int, int, int>, int> was;
    VEVE(i, 0, n) {
      auto& c = circs[i];
      c.x = next_int();
      c.y = next_int();
      c.r = next_int();
//      cin >> c.x >> c.y >> c.r;
      c.id = i;
      int& w = was[make_tuple(c.x, c.y, c.r)];
      if (w > 0) {
        res[i] = -w;
      } else {
        w = i + 1;
      }
    }
  }
  const int PW = 1 << 30;
  Node* root = Node::pool + Node::Alloc(-PW, -PW, PW, PW);
  vector<int> ord(n);
  iota(ALL(ord), 0);
  sort(ALL(ord), [&](int a, int b) {
    return circs[a] < circs[b];
  });
  set<int> rem_ids;
  VEVE(i, 0, n) if (res[ord[i]] == -(n + 1)) rem_ids.insert(i);
  VEVE(its, 0, min(n, (int) (1e7) / n)) {
    if (rem_ids.empty())
      break;
    const auto& c = circs[ord[*rem_ids.begin()]];
    for (auto it = rem_ids.begin(); it != rem_ids.end();) {
      if (c.Intersects(circs[ord[*it]])) {
        res[ord[*it]] = c.id;
        rem_ids.erase(it++);
      } else {
        ++it;
      }
    }
  }
  vector<Circle> rem;
  rem.reserve(n);
  RARA(i, rem_ids) {
    rem.push_back(circs[ord[i]]);
//    DEBUG(i + 1);
  }
  root->Insert(rem);
  RARA(c, rem) if (res[c.id] == -(n + 1)) {
      root->Erase(c, circs, res);
    }
  RARA(r, res) if (r < 0) r = res[-r - 1];
  RARA(r, res) {
//    cout << (r + 1) << ' ';
    write_int(r + 1);
    write_char(' ');
  }
//  cout << endl;
  write_char('\n');
  write_flush();
}

void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
}

int32_t

main() {
#ifdef AZN
  freopen("input.txt", "r", stdin);
#endif
  Init();
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	538 ms	657928 KB	Output is correct
2	Correct	519 ms	657928 KB	Output is correct
3	Correct	542 ms	657928 KB	Output is correct
4	Correct	566 ms	658092 KB	Output is correct
5	Correct	537 ms	658092 KB	Output is correct
6	Correct	538 ms	658092 KB	Output is correct
7	Correct	553 ms	658092 KB	Output is correct
8	Correct	600 ms	658092 KB	Output is correct
9	Correct	583 ms	658300 KB	Output is correct
10	Correct	570 ms	658300 KB	Output is correct
11	Correct	611 ms	658300 KB	Output is correct
12	Correct	546 ms	658300 KB	Output is correct
13	Correct	532 ms	658300 KB	Output is correct
14	Correct	552 ms	658300 KB	Output is correct
15	Correct	563 ms	658300 KB	Output is correct
16	Correct	561 ms	658308 KB	Output is correct
17	Correct	559 ms	658308 KB	Output is correct
18	Correct	549 ms	658308 KB	Output is correct
19	Correct	519 ms	658668 KB	Output is correct
20	Correct	570 ms	658708 KB	Output is correct
21	Correct	553 ms	658780 KB	Output is correct
22	Correct	589 ms	658788 KB	Output is correct
23	Correct	619 ms	658788 KB	Output is correct
24	Correct	618 ms	658820 KB	Output is correct
25	Correct	622 ms	658820 KB	Output is correct
26	Correct	584 ms	658932 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1174 ms	685024 KB	Output is correct
2	Correct	1104 ms	685024 KB	Output is correct
3	Correct	1024 ms	685024 KB	Output is correct
4	Correct	1025 ms	685048 KB	Output is correct
5	Correct	1785 ms	761472 KB	Output is correct
6	Correct	2084 ms	761472 KB	Output is correct
7	Correct	1755 ms	761472 KB	Output is correct
8	Correct	1975 ms	761472 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	554 ms	761472 KB	Output is correct
2	Correct	1074 ms	761472 KB	Output is correct
3	Correct	2908 ms	761472 KB	Output is correct
4	Correct	2841 ms	761472 KB	Output is correct
5	Correct	2053 ms	761472 KB	Output is correct
6	Correct	1332 ms	761472 KB	Output is correct
7	Correct	885 ms	761472 KB	Output is correct
8	Correct	659 ms	761472 KB	Output is correct
9	Correct	2621 ms	761472 KB	Output is correct
10	Correct	2555 ms	761472 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2305 ms	761472 KB	Output is correct
2	Correct	2663 ms	761472 KB	Output is correct
3	Correct	1600 ms	761472 KB	Output is correct
4	Correct	2213 ms	761472 KB	Output is correct
5	Correct	2376 ms	761472 KB	Output is correct
6	Correct	1704 ms	761472 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	538 ms	657928 KB	Output is correct
2	Correct	519 ms	657928 KB	Output is correct
3	Correct	542 ms	657928 KB	Output is correct
4	Correct	566 ms	658092 KB	Output is correct
5	Correct	537 ms	658092 KB	Output is correct
6	Correct	538 ms	658092 KB	Output is correct
7	Correct	553 ms	658092 KB	Output is correct
8	Correct	600 ms	658092 KB	Output is correct
9	Correct	583 ms	658300 KB	Output is correct
10	Correct	570 ms	658300 KB	Output is correct
11	Correct	611 ms	658300 KB	Output is correct
12	Correct	546 ms	658300 KB	Output is correct
13	Correct	532 ms	658300 KB	Output is correct
14	Correct	552 ms	658300 KB	Output is correct
15	Correct	563 ms	658300 KB	Output is correct
16	Correct	561 ms	658308 KB	Output is correct
17	Correct	559 ms	658308 KB	Output is correct
18	Correct	549 ms	658308 KB	Output is correct
19	Correct	519 ms	658668 KB	Output is correct
20	Correct	570 ms	658708 KB	Output is correct
21	Correct	553 ms	658780 KB	Output is correct
22	Correct	589 ms	658788 KB	Output is correct
23	Correct	619 ms	658788 KB	Output is correct
24	Correct	618 ms	658820 KB	Output is correct
25	Correct	622 ms	658820 KB	Output is correct
26	Correct	584 ms	658932 KB	Output is correct
27	Correct	560 ms	761472 KB	Output is correct
28	Correct	545 ms	761472 KB	Output is correct
29	Correct	577 ms	761472 KB	Output is correct
30	Correct	683 ms	761472 KB	Output is correct
31	Correct	673 ms	761472 KB	Output is correct
32	Correct	682 ms	761472 KB	Output is correct
33	Correct	746 ms	761472 KB	Output is correct
34	Correct	725 ms	761472 KB	Output is correct
35	Correct	727 ms	761472 KB	Output is correct
36	Correct	988 ms	761472 KB	Output is correct
37	Correct	1062 ms	761472 KB	Output is correct
38	Correct	956 ms	761472 KB	Output is correct
39	Correct	908 ms	761472 KB	Output is correct
40	Correct	1002 ms	761472 KB	Output is correct
41	Correct	1014 ms	761472 KB	Output is correct
42	Correct	938 ms	761472 KB	Output is correct
43	Correct	1102 ms	761472 KB	Output is correct
44	Correct	1184 ms	761472 KB	Output is correct
45	Correct	1202 ms	761472 KB	Output is correct
46	Correct	1186 ms	761472 KB	Output is correct
47	Correct	931 ms	761472 KB	Output is correct
48	Correct	879 ms	761472 KB	Output is correct
49	Correct	913 ms	761472 KB	Output is correct
50	Correct	894 ms	761472 KB	Output is correct

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	538 ms	657928 KB	Output is correct
2	Correct	519 ms	657928 KB	Output is correct
3	Correct	542 ms	657928 KB	Output is correct
4	Correct	566 ms	658092 KB	Output is correct
5	Correct	537 ms	658092 KB	Output is correct
6	Correct	538 ms	658092 KB	Output is correct
7	Correct	553 ms	658092 KB	Output is correct
8	Correct	600 ms	658092 KB	Output is correct
9	Correct	583 ms	658300 KB	Output is correct
10	Correct	570 ms	658300 KB	Output is correct
11	Correct	611 ms	658300 KB	Output is correct
12	Correct	546 ms	658300 KB	Output is correct
13	Correct	532 ms	658300 KB	Output is correct
14	Correct	552 ms	658300 KB	Output is correct
15	Correct	563 ms	658300 KB	Output is correct
16	Correct	561 ms	658308 KB	Output is correct
17	Correct	559 ms	658308 KB	Output is correct
18	Correct	549 ms	658308 KB	Output is correct
19	Correct	519 ms	658668 KB	Output is correct
20	Correct	570 ms	658708 KB	Output is correct
21	Correct	553 ms	658780 KB	Output is correct
22	Correct	589 ms	658788 KB	Output is correct
23	Correct	619 ms	658788 KB	Output is correct
24	Correct	618 ms	658820 KB	Output is correct
25	Correct	622 ms	658820 KB	Output is correct
26	Correct	584 ms	658932 KB	Output is correct
27	Correct	1174 ms	685024 KB	Output is correct
28	Correct	1104 ms	685024 KB	Output is correct
29	Correct	1024 ms	685024 KB	Output is correct
30	Correct	1025 ms	685048 KB	Output is correct
31	Correct	1785 ms	761472 KB	Output is correct
32	Correct	2084 ms	761472 KB	Output is correct
33	Correct	1755 ms	761472 KB	Output is correct
34	Correct	1975 ms	761472 KB	Output is correct
35	Correct	554 ms	761472 KB	Output is correct
36	Correct	1074 ms	761472 KB	Output is correct
37	Correct	2908 ms	761472 KB	Output is correct
38	Correct	2841 ms	761472 KB	Output is correct
39	Correct	2053 ms	761472 KB	Output is correct
40	Correct	1332 ms	761472 KB	Output is correct
41	Correct	885 ms	761472 KB	Output is correct
42	Correct	659 ms	761472 KB	Output is correct
43	Correct	2621 ms	761472 KB	Output is correct
44	Correct	2555 ms	761472 KB	Output is correct
45	Correct	2305 ms	761472 KB	Output is correct
46	Correct	2663 ms	761472 KB	Output is correct
47	Correct	1600 ms	761472 KB	Output is correct
48	Correct	2213 ms	761472 KB	Output is correct
49	Correct	2376 ms	761472 KB	Output is correct
50	Correct	1704 ms	761472 KB	Output is correct
51	Correct	560 ms	761472 KB	Output is correct
52	Correct	545 ms	761472 KB	Output is correct
53	Correct	577 ms	761472 KB	Output is correct
54	Correct	683 ms	761472 KB	Output is correct
55	Correct	673 ms	761472 KB	Output is correct
56	Correct	682 ms	761472 KB	Output is correct
57	Correct	746 ms	761472 KB	Output is correct
58	Correct	725 ms	761472 KB	Output is correct
59	Correct	727 ms	761472 KB	Output is correct
60	Correct	988 ms	761472 KB	Output is correct
61	Correct	1062 ms	761472 KB	Output is correct
62	Correct	956 ms	761472 KB	Output is correct
63	Correct	908 ms	761472 KB	Output is correct
64	Correct	1002 ms	761472 KB	Output is correct
65	Correct	1014 ms	761472 KB	Output is correct
66	Correct	938 ms	761472 KB	Output is correct
67	Correct	1102 ms	761472 KB	Output is correct
68	Correct	1184 ms	761472 KB	Output is correct
69	Correct	1202 ms	761472 KB	Output is correct
70	Correct	1186 ms	761472 KB	Output is correct
71	Correct	931 ms	761472 KB	Output is correct
72	Correct	879 ms	761472 KB	Output is correct
73	Correct	913 ms	761472 KB	Output is correct
74	Correct	894 ms	761472 KB	Output is correct
75	Correct	1084 ms	761472 KB	Output is correct
76	Correct	1242 ms	761472 KB	Output is correct
77	Correct	1214 ms	761472 KB	Output is correct
78	Correct	1082 ms	761472 KB	Output is correct
79	Correct	1324 ms	761472 KB	Output is correct
80	Correct	1237 ms	761472 KB	Output is correct
81	Correct	2855 ms	761472 KB	Output is correct
82	Correct	2579 ms	761472 KB	Output is correct
83	Correct	2396 ms	761472 KB	Output is correct
84	Correct	2707 ms	761472 KB	Output is correct
85	Correct	2476 ms	761472 KB	Output is correct
86	Correct	2228 ms	761472 KB	Output is correct
87	Correct	2254 ms	761472 KB	Output is correct
88	Correct	1627 ms	761472 KB	Output is correct
89	Correct	1636 ms	761472 KB	Output is correct
90	Correct	1775 ms	761472 KB	Output is correct
91	Correct	2109 ms	761472 KB	Output is correct
92	Correct	1703 ms	761472 KB	Output is correct
93	Execution timed out	3033 ms	761472 KB	Time limit exceeded
94	Halted	0 ms	0 KB	-

답안 #48955

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