oj.uz

Submission #48955

# Submission time Handle Problem Language Result Execution time Memory
48955 2018-05-20T10:18:27 Z azneye Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 761472 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -