#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300000;
int xc[1+MAX_N], yc[1+MAX_N], rc[1+MAX_N];
int poz[1+MAX_N], rez[1+MAX_N];
double ld[1+MAX_N], rd[1+MAX_N];
set<pair<double, int>> sl, sr;
bool cmp(int a, int b) {
return rc[a] > rc[b] || (rc[a] == rc[b] && a < b);
}
double dist(int xa, int ya, int xb, int yb) {
return sqrt((long long)(xa - xb) * (xa - xb) +
(long long)(ya - yb) * (ya - yb));
}
int main() {
#ifdef HOME
FILE *fin = fopen("input.in", "r");
FILE *fout = fopen("output.out", "w");
#else
FILE *fin = stdin;
FILE *fout = stdout;
#endif
int n, ox, oy;
ox = -2000000000;
oy = -2000000000;
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; ++i) {
fscanf(fin, "%d%d%d", &xc[i], &yc[i], &rc[i]);
double d = dist(ox, oy, xc[i], yc[i]);
ld[i] = d - rc[i];
rd[i] = d + rc[i];
sl.insert(make_pair(ld[i], i));
sr.insert(make_pair(rd[i], i));
poz[i - 1] = i;
}
sort(poz, poz + n, cmp);
for(int i = 0; i < n; ++i) {
int x = poz[i];
if(rez[x] == 0) {
set<pair<double, int> >::iterator it;
it = sl.lower_bound(make_pair(ld[x], -1));
while(it != sl.end() && it->first <= rd[x]) {
int todel = it->second;
if(rc[x] + rc[todel] >= dist(xc[x], yc[x], xc[todel], yc[todel])) {
rez[todel] = x;
sr.erase(make_pair(rd[todel], todel));
it = sl.erase(it);
} else
it++;
}
it = sr.lower_bound(make_pair(ld[x], -1));
while(it != sr.end() && it->first <= rd[x]) {
int todel = it->second;
if(rc[x] + rc[todel] >= dist(xc[x], yc[x], xc[todel], yc[todel])) {
rez[todel] = x;
sl.erase(make_pair(ld[todel], todel));
it = sr.erase(it);
} else
it++;
}
}
}
for(int i = 1; i <= n; ++i)
fprintf(fout, "%d ", rez[i]);
#ifdef HOME
fclose(fin);
fclose(fout);
#endif
return 0;
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:34:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d", &n);
~~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:36:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d%d%d", &xc[i], &yc[i], &rc[i]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
500 KB |
Output is correct |
| 3 |
Correct |
2 ms |
500 KB |
Output is correct |
| 4 |
Correct |
2 ms |
500 KB |
Output is correct |
| 5 |
Correct |
2 ms |
500 KB |
Output is correct |
| 6 |
Correct |
2 ms |
500 KB |
Output is correct |
| 7 |
Correct |
2 ms |
516 KB |
Output is correct |
| 8 |
Correct |
2 ms |
532 KB |
Output is correct |
| 9 |
Correct |
2 ms |
532 KB |
Output is correct |
| 10 |
Correct |
2 ms |
548 KB |
Output is correct |
| 11 |
Correct |
2 ms |
600 KB |
Output is correct |
| 12 |
Correct |
2 ms |
600 KB |
Output is correct |
| 13 |
Correct |
2 ms |
600 KB |
Output is correct |
| 14 |
Correct |
2 ms |
600 KB |
Output is correct |
| 15 |
Correct |
2 ms |
600 KB |
Output is correct |
| 16 |
Correct |
3 ms |
956 KB |
Output is correct |
| 17 |
Correct |
3 ms |
956 KB |
Output is correct |
| 18 |
Correct |
3 ms |
956 KB |
Output is correct |
| 19 |
Correct |
9 ms |
1628 KB |
Output is correct |
| 20 |
Correct |
13 ms |
1648 KB |
Output is correct |
| 21 |
Correct |
9 ms |
1664 KB |
Output is correct |
| 22 |
Correct |
10 ms |
1680 KB |
Output is correct |
| 23 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 24 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 25 |
Correct |
9 ms |
1764 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1273 ms |
51108 KB |
Output is correct |
| 2 |
Correct |
1382 ms |
51260 KB |
Output is correct |
| 3 |
Correct |
1175 ms |
51260 KB |
Output is correct |
| 4 |
Correct |
1271 ms |
51324 KB |
Output is correct |
| 5 |
Correct |
1014 ms |
51324 KB |
Output is correct |
| 6 |
Correct |
1127 ms |
51324 KB |
Output is correct |
| 7 |
Correct |
1278 ms |
51324 KB |
Output is correct |
| 8 |
Correct |
1211 ms |
51324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
51324 KB |
Output is correct |
| 2 |
Correct |
666 ms |
51324 KB |
Output is correct |
| 3 |
Correct |
2871 ms |
51324 KB |
Output is correct |
| 4 |
Execution timed out |
3036 ms |
57404 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1628 ms |
59208 KB |
Output is correct |
| 2 |
Correct |
1323 ms |
59208 KB |
Output is correct |
| 3 |
Execution timed out |
3018 ms |
59208 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
500 KB |
Output is correct |
| 3 |
Correct |
2 ms |
500 KB |
Output is correct |
| 4 |
Correct |
2 ms |
500 KB |
Output is correct |
| 5 |
Correct |
2 ms |
500 KB |
Output is correct |
| 6 |
Correct |
2 ms |
500 KB |
Output is correct |
| 7 |
Correct |
2 ms |
516 KB |
Output is correct |
| 8 |
Correct |
2 ms |
532 KB |
Output is correct |
| 9 |
Correct |
2 ms |
532 KB |
Output is correct |
| 10 |
Correct |
2 ms |
548 KB |
Output is correct |
| 11 |
Correct |
2 ms |
600 KB |
Output is correct |
| 12 |
Correct |
2 ms |
600 KB |
Output is correct |
| 13 |
Correct |
2 ms |
600 KB |
Output is correct |
| 14 |
Correct |
2 ms |
600 KB |
Output is correct |
| 15 |
Correct |
2 ms |
600 KB |
Output is correct |
| 16 |
Correct |
3 ms |
956 KB |
Output is correct |
| 17 |
Correct |
3 ms |
956 KB |
Output is correct |
| 18 |
Correct |
3 ms |
956 KB |
Output is correct |
| 19 |
Correct |
9 ms |
1628 KB |
Output is correct |
| 20 |
Correct |
13 ms |
1648 KB |
Output is correct |
| 21 |
Correct |
9 ms |
1664 KB |
Output is correct |
| 22 |
Correct |
10 ms |
1680 KB |
Output is correct |
| 23 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 24 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 25 |
Correct |
9 ms |
1764 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 27 |
Correct |
18 ms |
59208 KB |
Output is correct |
| 28 |
Correct |
19 ms |
59208 KB |
Output is correct |
| 29 |
Correct |
17 ms |
59208 KB |
Output is correct |
| 30 |
Correct |
21 ms |
59208 KB |
Output is correct |
| 31 |
Correct |
20 ms |
59208 KB |
Output is correct |
| 32 |
Correct |
20 ms |
59208 KB |
Output is correct |
| 33 |
Correct |
289 ms |
59208 KB |
Output is correct |
| 34 |
Correct |
281 ms |
59208 KB |
Output is correct |
| 35 |
Correct |
326 ms |
59208 KB |
Output is correct |
| 36 |
Correct |
440 ms |
59208 KB |
Output is correct |
| 37 |
Correct |
413 ms |
59208 KB |
Output is correct |
| 38 |
Correct |
469 ms |
59208 KB |
Output is correct |
| 39 |
Correct |
1921 ms |
59208 KB |
Output is correct |
| 40 |
Correct |
2075 ms |
59208 KB |
Output is correct |
| 41 |
Correct |
1905 ms |
59208 KB |
Output is correct |
| 42 |
Correct |
777 ms |
59208 KB |
Output is correct |
| 43 |
Correct |
282 ms |
59208 KB |
Output is correct |
| 44 |
Correct |
260 ms |
59208 KB |
Output is correct |
| 45 |
Correct |
321 ms |
59208 KB |
Output is correct |
| 46 |
Correct |
291 ms |
59208 KB |
Output is correct |
| 47 |
Correct |
285 ms |
59208 KB |
Output is correct |
| 48 |
Correct |
284 ms |
59208 KB |
Output is correct |
| 49 |
Correct |
284 ms |
59208 KB |
Output is correct |
| 50 |
Correct |
350 ms |
59208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
500 KB |
Output is correct |
| 3 |
Correct |
2 ms |
500 KB |
Output is correct |
| 4 |
Correct |
2 ms |
500 KB |
Output is correct |
| 5 |
Correct |
2 ms |
500 KB |
Output is correct |
| 6 |
Correct |
2 ms |
500 KB |
Output is correct |
| 7 |
Correct |
2 ms |
516 KB |
Output is correct |
| 8 |
Correct |
2 ms |
532 KB |
Output is correct |
| 9 |
Correct |
2 ms |
532 KB |
Output is correct |
| 10 |
Correct |
2 ms |
548 KB |
Output is correct |
| 11 |
Correct |
2 ms |
600 KB |
Output is correct |
| 12 |
Correct |
2 ms |
600 KB |
Output is correct |
| 13 |
Correct |
2 ms |
600 KB |
Output is correct |
| 14 |
Correct |
2 ms |
600 KB |
Output is correct |
| 15 |
Correct |
2 ms |
600 KB |
Output is correct |
| 16 |
Correct |
3 ms |
956 KB |
Output is correct |
| 17 |
Correct |
3 ms |
956 KB |
Output is correct |
| 18 |
Correct |
3 ms |
956 KB |
Output is correct |
| 19 |
Correct |
9 ms |
1628 KB |
Output is correct |
| 20 |
Correct |
13 ms |
1648 KB |
Output is correct |
| 21 |
Correct |
9 ms |
1664 KB |
Output is correct |
| 22 |
Correct |
10 ms |
1680 KB |
Output is correct |
| 23 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 24 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 25 |
Correct |
9 ms |
1764 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1764 KB |
Output is correct |
| 27 |
Correct |
1273 ms |
51108 KB |
Output is correct |
| 28 |
Correct |
1382 ms |
51260 KB |
Output is correct |
| 29 |
Correct |
1175 ms |
51260 KB |
Output is correct |
| 30 |
Correct |
1271 ms |
51324 KB |
Output is correct |
| 31 |
Correct |
1014 ms |
51324 KB |
Output is correct |
| 32 |
Correct |
1127 ms |
51324 KB |
Output is correct |
| 33 |
Correct |
1278 ms |
51324 KB |
Output is correct |
| 34 |
Correct |
1211 ms |
51324 KB |
Output is correct |
| 35 |
Correct |
2 ms |
51324 KB |
Output is correct |
| 36 |
Correct |
666 ms |
51324 KB |
Output is correct |
| 37 |
Correct |
2871 ms |
51324 KB |
Output is correct |
| 38 |
Execution timed out |
3036 ms |
57404 KB |
Time limit exceeded |
| 39 |
Halted |
0 ms |
0 KB |
- |
