#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;
srand(time(NULL));
ox = rand() % 2000000001 - 1000000000;
oy = rand() % 2000000001 - 1000000000;
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((long long)(rc[x] + rc[todel]) * (rc[x] + rc[todel]) >=
(long long)(xc[x] - xc[todel]) * (xc[x] - xc[todel]) +
(long long)(yc[x] - yc[todel]) * (yc[x] - 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((long long)(rc[x] + rc[todel]) * (rc[x] + rc[todel]) >=
(long long)(xc[x] - xc[todel]) * (xc[x] - xc[todel]) +
(long long)(yc[x] - yc[todel]) * (yc[x] - 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:36: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:38: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 |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
2 ms |
524 KB |
Output is correct |
| 5 |
Correct |
2 ms |
524 KB |
Output is correct |
| 6 |
Correct |
2 ms |
600 KB |
Output is correct |
| 7 |
Correct |
2 ms |
616 KB |
Output is correct |
| 8 |
Correct |
2 ms |
616 KB |
Output is correct |
| 9 |
Correct |
2 ms |
744 KB |
Output is correct |
| 10 |
Correct |
2 ms |
744 KB |
Output is correct |
| 11 |
Correct |
2 ms |
744 KB |
Output is correct |
| 12 |
Correct |
2 ms |
744 KB |
Output is correct |
| 13 |
Correct |
2 ms |
744 KB |
Output is correct |
| 14 |
Correct |
2 ms |
744 KB |
Output is correct |
| 15 |
Correct |
2 ms |
744 KB |
Output is correct |
| 16 |
Correct |
3 ms |
792 KB |
Output is correct |
| 17 |
Correct |
3 ms |
824 KB |
Output is correct |
| 18 |
Correct |
3 ms |
856 KB |
Output is correct |
| 19 |
Correct |
8 ms |
1660 KB |
Output is correct |
| 20 |
Correct |
8 ms |
1848 KB |
Output is correct |
| 21 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 22 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 23 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 24 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 25 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1244 ms |
51364 KB |
Output is correct |
| 2 |
Correct |
1414 ms |
51372 KB |
Output is correct |
| 3 |
Correct |
1167 ms |
51372 KB |
Output is correct |
| 4 |
Correct |
1138 ms |
51372 KB |
Output is correct |
| 5 |
Correct |
903 ms |
51372 KB |
Output is correct |
| 6 |
Correct |
967 ms |
51372 KB |
Output is correct |
| 7 |
Correct |
926 ms |
51416 KB |
Output is correct |
| 8 |
Correct |
920 ms |
51416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
51416 KB |
Output is correct |
| 2 |
Correct |
510 ms |
51416 KB |
Output is correct |
| 3 |
Correct |
2287 ms |
51416 KB |
Output is correct |
| 4 |
Correct |
2878 ms |
51416 KB |
Output is correct |
| 5 |
Correct |
2240 ms |
57884 KB |
Output is correct |
| 6 |
Correct |
764 ms |
57884 KB |
Output is correct |
| 7 |
Correct |
367 ms |
57884 KB |
Output is correct |
| 8 |
Correct |
39 ms |
57884 KB |
Output is correct |
| 9 |
Correct |
2668 ms |
74524 KB |
Output is correct |
| 10 |
Execution timed out |
3042 ms |
81052 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1489 ms |
83212 KB |
Output is correct |
| 2 |
Correct |
1059 ms |
83212 KB |
Output is correct |
| 3 |
Execution timed out |
3029 ms |
83212 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 |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
2 ms |
524 KB |
Output is correct |
| 5 |
Correct |
2 ms |
524 KB |
Output is correct |
| 6 |
Correct |
2 ms |
600 KB |
Output is correct |
| 7 |
Correct |
2 ms |
616 KB |
Output is correct |
| 8 |
Correct |
2 ms |
616 KB |
Output is correct |
| 9 |
Correct |
2 ms |
744 KB |
Output is correct |
| 10 |
Correct |
2 ms |
744 KB |
Output is correct |
| 11 |
Correct |
2 ms |
744 KB |
Output is correct |
| 12 |
Correct |
2 ms |
744 KB |
Output is correct |
| 13 |
Correct |
2 ms |
744 KB |
Output is correct |
| 14 |
Correct |
2 ms |
744 KB |
Output is correct |
| 15 |
Correct |
2 ms |
744 KB |
Output is correct |
| 16 |
Correct |
3 ms |
792 KB |
Output is correct |
| 17 |
Correct |
3 ms |
824 KB |
Output is correct |
| 18 |
Correct |
3 ms |
856 KB |
Output is correct |
| 19 |
Correct |
8 ms |
1660 KB |
Output is correct |
| 20 |
Correct |
8 ms |
1848 KB |
Output is correct |
| 21 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 22 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 23 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 24 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 25 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1944 KB |
Output is correct |
| 27 |
Correct |
18 ms |
83212 KB |
Output is correct |
| 28 |
Correct |
17 ms |
83212 KB |
Output is correct |
| 29 |
Correct |
18 ms |
83212 KB |
Output is correct |
| 30 |
Correct |
21 ms |
83212 KB |
Output is correct |
| 31 |
Correct |
22 ms |
83212 KB |
Output is correct |
| 32 |
Correct |
21 ms |
83212 KB |
Output is correct |
| 33 |
Correct |
318 ms |
83212 KB |
Output is correct |
| 34 |
Correct |
347 ms |
83212 KB |
Output is correct |
| 35 |
Correct |
332 ms |
83212 KB |
Output is correct |
| 36 |
Correct |
475 ms |
83212 KB |
Output is correct |
| 37 |
Correct |
431 ms |
83212 KB |
Output is correct |
| 38 |
Correct |
509 ms |
83212 KB |
Output is correct |
| 39 |
Correct |
1815 ms |
83212 KB |
Output is correct |
| 40 |
Correct |
1726 ms |
83212 KB |
Output is correct |
| 41 |
Correct |
1544 ms |
83212 KB |
Output is correct |
| 42 |
Correct |
816 ms |
83212 KB |
Output is correct |
| 43 |
Correct |
280 ms |
83212 KB |
Output is correct |
| 44 |
Correct |
258 ms |
83212 KB |
Output is correct |
| 45 |
Correct |
304 ms |
83212 KB |
Output is correct |
| 46 |
Correct |
301 ms |
83212 KB |
Output is correct |
| 47 |
Correct |
329 ms |
83212 KB |
Output is correct |
| 48 |
Correct |
270 ms |
83212 KB |
Output is correct |
| 49 |
Correct |
327 ms |
83212 KB |
Output is correct |
| 50 |
Correct |
293 ms |
83212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
2 ms |
524 KB |
Output is correct |
| 5 |
Correct |
2 ms |
524 KB |
Output is correct |
| 6 |
Correct |
2 ms |
600 KB |
Output is correct |
| 7 |
Correct |
2 ms |
616 KB |
Output is correct |
| 8 |
Correct |
2 ms |
616 KB |
Output is correct |
| 9 |
Correct |
2 ms |
744 KB |
Output is correct |
| 10 |
Correct |
2 ms |
744 KB |
Output is correct |
| 11 |
Correct |
2 ms |
744 KB |
Output is correct |
| 12 |
Correct |
2 ms |
744 KB |
Output is correct |
| 13 |
Correct |
2 ms |
744 KB |
Output is correct |
| 14 |
Correct |
2 ms |
744 KB |
Output is correct |
| 15 |
Correct |
2 ms |
744 KB |
Output is correct |
| 16 |
Correct |
3 ms |
792 KB |
Output is correct |
| 17 |
Correct |
3 ms |
824 KB |
Output is correct |
| 18 |
Correct |
3 ms |
856 KB |
Output is correct |
| 19 |
Correct |
8 ms |
1660 KB |
Output is correct |
| 20 |
Correct |
8 ms |
1848 KB |
Output is correct |
| 21 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 22 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 23 |
Correct |
9 ms |
1868 KB |
Output is correct |
| 24 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 25 |
Correct |
10 ms |
1868 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1944 KB |
Output is correct |
| 27 |
Correct |
1244 ms |
51364 KB |
Output is correct |
| 28 |
Correct |
1414 ms |
51372 KB |
Output is correct |
| 29 |
Correct |
1167 ms |
51372 KB |
Output is correct |
| 30 |
Correct |
1138 ms |
51372 KB |
Output is correct |
| 31 |
Correct |
903 ms |
51372 KB |
Output is correct |
| 32 |
Correct |
967 ms |
51372 KB |
Output is correct |
| 33 |
Correct |
926 ms |
51416 KB |
Output is correct |
| 34 |
Correct |
920 ms |
51416 KB |
Output is correct |
| 35 |
Correct |
2 ms |
51416 KB |
Output is correct |
| 36 |
Correct |
510 ms |
51416 KB |
Output is correct |
| 37 |
Correct |
2287 ms |
51416 KB |
Output is correct |
| 38 |
Correct |
2878 ms |
51416 KB |
Output is correct |
| 39 |
Correct |
2240 ms |
57884 KB |
Output is correct |
| 40 |
Correct |
764 ms |
57884 KB |
Output is correct |
| 41 |
Correct |
367 ms |
57884 KB |
Output is correct |
| 42 |
Correct |
39 ms |
57884 KB |
Output is correct |
| 43 |
Correct |
2668 ms |
74524 KB |
Output is correct |
| 44 |
Execution timed out |
3042 ms |
81052 KB |
Time limit exceeded |
