제출 #1175009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175009		JelalTkm	원 고르기 (APIO18_circle_selection)	C++20	19 / 100	2912 ms	892368 KiB

circle_selection

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 50000 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

struct node {
  int x;
  int y;
  int c;
  int nu;
};

bool cmp(node &t1, node &t2) {
  return ((t1.c > t2.c) || (t1.c == t2.c && t1.nu < t2.nu));
}

int sq(int n) {
  return (n * n);
}

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int n;
    cin >> n;
    if (n <= 5000) {
      vector<int> ans(n + 1);
      vector<node> a(n + 1);
      for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].c;
        a[i].nu = i;
      }

      sort(a.begin(), a.end(), cmp);
      for (int i = 0; i < n; i++) {
        if (!ans[a[i].nu]) {
          ans[a[i].nu] = a[i].nu;
          for (int j = i + 1; j < n; j++) {
            if ((sq(a[i].x - a[j].x) + sq(a[i].y - a[j].y)) <= sq(a[i].c + a[j].c) && !ans[a[j].nu]) {
              ans[a[j].nu] = a[i].nu; 
            }
          }
        }
      }

      for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
      cout << '\n';
    } else {
      vector<node> order(n + 1), a(n + 1);
      bool ok = 1;
      for (int i = 1; i <= n; i++) {
        cin >> order[i].x >> order[i].y >> order[i].c;
        order[i].nu = i;
        if (order[i].y != 0)
          ok = 0;
        a[i] = order[i];
      }

      if (!ok) {
        int rd = order[1].c;
        vector<int> ans(n + 1);
        map<pair<int, int>, set<int>> mp;
        for (int i = 1; i <= n; i++)
          mp[{(order[i].x / rd), (order[i].y / rd)}].insert(i);

        for (int i = 1; i <= n; i++) {
          int x1 = order[i].x, y1 = order[i].y;
          if (!ans[i]) {
            for (int x = x1 - 2; x <= x1 + 2; x++)
              for (int y = y1 - 2; y <= y1 + 2; y++) {
                auto l = mp[{x, y}].begin();
                while (l != mp[{x, y}].end()) {
                  ans[*l] = i;
                  l = mp[{x, y}].erase(l);
                }
              }
            ans[i] = i;
          }
        }

        for (int i = 1; i <= n; i++)
          cout << ans[i] << " ";
        continue;
      }

      set<pair<int, int>> L, R;
      for (int i = 1; i <= n; i++) {
        L.insert({order[i].x - order[i].c, i});
        R.insert({order[i].x + order[i].c, i});
      }
      sort(order.begin(), order.end(), cmp);
      vector<int> ans(n + 1);
      for (int i = 0; i < n; i++) {
        if (!ans[order[i].nu]) {
          auto l = L.lower_bound({order[i].x - order[i].c, 0});
          while (l != L.end() && l->first <= (order[i].x + order[i].c)) {
            ans[l->second] = order[i].nu;
            R.erase({a[l->second].x + a[l->second].c, l->second});
            l = L.erase(l);
          }

          auto r = R.lower_bound({order[i].x + order[i].c + 1, 0});
          while (r != R.begin()) {
            r--;
            if (r->first < (order[i].x - order[i].c)) break;
            ans[r->second] = order[i].nu;
            L.erase({a[r->second].x - a[r->second].c, r->second});
            r = R.erase(r);
          }
          ans[order[i].nu] = order[i].nu;
        }
      }

      for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    }
  }

  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13