Submission #1173355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173355		JelalTkm	Circle selection (APIO18_circle_selection)	C++20	7 / 100	15 ms	584 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';
    }
  }

  return 0;
}

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