Submission #797394

#	Time	Username	Problem	Language	Result	Execution time	Memory
797394		radaiosm7	Circle selection (APIO18_circle_selection)	C++98	7 / 100	3085 ms	19632 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, i, j, curr, chk;
long long R1, R2;
int ans[300005];
pair<long long, int> rd[300005];
pair<long long, long long> pnt[300005];

bool cmp(const pair<long long, int>& a, const pair<long long, int>& b) {
  if (a.X == b.X) return a.Y < b.Y;
  else return a.X > b.X;
}

bool val(int x, int y) {
  return (pnt[x].X-pnt[y].X)*(pnt[x].X-pnt[y].X) + (pnt[x].Y-pnt[y].Y)*(pnt[x].Y-pnt[y].Y) <= (R1+R2)*(R1+R2);
}

int main() {
  scanf("%d", &n);

  for (i=1; i <= n; ++i) {
    scanf("%lld%lld%lld", &pnt[i].X, &pnt[i].Y, &rd[i].X);
    rd[i].Y = i;
  }

  sort(rd+1, rd+n+1, cmp);
  fill(ans, ans+n+1, -1);

  for (i=1; i <= n; ++i) {
    curr = rd[i].Y;
    R1 = rd[i].X;

    if (ans[curr] == -1) {
      ans[curr] = curr;
      
      for (j=i+1; j <= n; ++j) {
        chk = rd[j].Y;
        R2 = rd[j].X;
        if (ans[chk] == -1 && val(curr, chk)) ans[chk] = curr;
      }
    }
  }
  
  for (i=1; i < n; ++i) printf("%d ", ans[i]);
  printf("%d\n", ans[n]);
  return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
circle_selection.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%lld%lld%lld", &pnt[i].X, &pnt[i].Y, &rd[i].X);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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