Submission #106502

#	Time	Username	Problem	Language	Result	Execution time	Memory
106502		bert30702	Circle selection (APIO18_circle_selection)	C++17	0 / 100	3035 ms	20152 KiB

circle_selection

    #include <bits/stdc++.h>
    #define pii pair<int, int>
    #define F first
    #define S second
    #define X real()
    #define Y imag()
    using namespace std;
    typedef complex<long double> C;
    const int MX = 3e5 + 100;
    struct circle { C p; int r, i; } v[MX];
    int ans[MX];
    main () {
    	srand(time(0));
    	int n; cin >> n;
    	for(int i = 1; i <= n; i ++) {
    		int x, y, r; cin >> x >> y >> r;
    		v[i] = {{x, y}, r, i};
    	}
    	double ang = rand() * 0.0001;
    	for(int i = 1; i <= n; i ++) v[i].p *= C{cos(ang), sin(ang)};
    	sort(v + 1, v + 1 + n, [](circle a, circle b) { return a.p.X < b.p.X; });
    	priority_queue<pii> pq;
    	for(int i = 1; i <= n; i ++) pq.push({v[i].r, -i});
    	while(pq.size()) {
    		pii p = pq.top(); pq.pop();
    		p.S = -p.S;
    		if(ans[v[p.S].i]) continue;
    		for(int i = max(1, p.S - 200); i <= min(n, p.S + 200); i ++) {
    			if(!ans[v[i].i] and abs(v[p.S].p - v[i].p) <= v[p.S].r + v[i].r) ans[v[i].i] = v[p.S].i;
    		}
    	}
    	for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';
    }

Compilation message (stderr)

circle_selection.cpp:12:11: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
     main () {
           ^
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:17:27: warning: narrowing conversion of 'x' from 'int' to 'long double' inside { } [-Wnarrowing]
       v[i] = {{x, y}, r, i};
                           ^
circle_selection.cpp:17:27: warning: narrowing conversion of 'y' from 'int' to 'long double' inside { } [-Wnarrowing]

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