oj.uz

Submission #99834

# Submission time Handle Problem Language Result Execution time Memory
99834 2019-03-07T17:16:51 Z TadijaSebez Circle selection (APIO18_circle_selection) C++11
7 / 100
 3000 ms 117836 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define mt make_tuple
struct circle{ ll x,y,r;int id;circle(){}circle(ll a, ll b, ll c):x(a),y(b),r(c){}};
ll sq(ll x){ return x*x;}
bool sec(circle a, circle b){ return sq(a.x-b.x)+sq(a.y-b.y)<=sq(a.r+b.r);}
bool operator < (circle a, circle b){ return a.r<b.r;}
const int N=300050;
const int mul=2e9+7;
circle a[N],b[N];
int ans[N];
vector<tuple<int,int,int>> all;
int main()
{
   	int n,i;
   	scanf("%i",&n);
   	for(i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].r),a[i].id=i,b[i]=a[i];
   	sort(a+1,a+1+n,[](circle a, circle b){ return a.r>b.r || a.r==b.r && a.id<b.id;});
   	for(int j=30;j>=0;j--)
   	{
   		int po=1<<j;
   		for(i=1;i<=n;i++) if(!ans[a[i].id])
   		{
   			pair<int,int> pa=mp(floor((double)a[i].x/po),floor((double)a[i].y/po));
   			all.pb(mt(pa.first,pa.second,a[i].id));
   		}
   		sort(all.begin(),all.end());
   		for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j-1))
   		{
   			int x=floor((double)a[i].x/po);
   			int y=floor((double)a[i].y/po);
   			for(int l=-2;l<=2;l++)
   			{
   				ll p=x+l;
   				int lb=upper_bound(all.begin(),all.end(),mt(x+l,y-3,mul))-all.begin();
   				//int rb=upper_bound(all[idx].begin(),all[idx].end(),mp(y+2,mul))-all[idx].begin();
   				for(int r=lb;r<all.size() && all[r]<=mt(x+l,y+2,mul);r++)
   				{
   					int c=get<2>(all[r]);
   					if(!ans[c] && sec(b[c],a[i])) ans[c]=a[i].id;
   				}
   			}
   		}
   	}
   	for(i=1;i<=n;i++) printf("%i%c",ans[i],i==n?'\n':' ');
   	return 0;
}

Compilation message

circle_selection.cpp: In lambda function:
circle_selection.cpp:21:71: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     sort(a+1,a+1+n,[](circle a, circle b){ return a.r>b.r || a.r==b.r && a.id<b.id;});
                                                              ~~~~~~~~~^~~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:31:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
      for(i=1;i<=n;i++) if(!ans[a[i].id] && a[i].r>=(1<<j-1))
                                                        ~^~
circle_selection.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int r=lb;r<all.size() && all[r]<=mt(x+l,y+2,mul);r++)
                     ~^~~~~~~~~~~
circle_selection.cpp:37:11: warning: unused variable 'p' [-Wunused-variable]
        ll p=x+l;
           ^
circle_selection.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
circle_selection.cpp:20:80: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].r),a[i].id=i,b[i]=a[i];
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 8 ms 512 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 10 ms 896 KB Output is correct
20 Correct 13 ms 916 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 75 ms 2288 KB Output is correct
23 Correct 70 ms 2296 KB Output is correct
24 Correct 210 ms 2384 KB Output is correct
25 Correct 279 ms 2316 KB Output is correct
26 Correct 90 ms 2288 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1306 ms 31548 KB Output is correct
2 Correct 1571 ms 33344 KB Output is correct
3 Correct 1430 ms 32840 KB Output is correct
4 Correct 741 ms 26120 KB Output is correct
5 Execution timed out 3059 ms 117836 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2746 ms 31532 KB Output is correct
3 Execution timed out 3049 ms 68524 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3056 ms 68536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 8 ms 512 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 10 ms 896 KB Output is correct
20 Correct 13 ms 916 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 75 ms 2288 KB Output is correct
23 Correct 70 ms 2296 KB Output is correct
24 Correct 210 ms 2384 KB Output is correct
25 Correct 279 ms 2316 KB Output is correct
26 Correct 90 ms 2288 KB Output is correct
27 Correct 26 ms 1468 KB Output is correct
28 Correct 32 ms 1532 KB Output is correct
29 Correct 30 ms 1472 KB Output is correct
30 Correct 164 ms 4220 KB Output is correct
31 Correct 145 ms 4200 KB Output is correct
32 Correct 146 ms 4200 KB Output is correct
33 Correct 262 ms 8972 KB Output is correct
34 Correct 258 ms 8868 KB Output is correct
35 Correct 505 ms 12896 KB Output is correct
36 Correct 1758 ms 31564 KB Output is correct
37 Correct 1690 ms 31452 KB Output is correct
38 Correct 1608 ms 31432 KB Output is correct
39 Execution timed out 3045 ms 56092 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 8 ms 512 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 10 ms 896 KB Output is correct
20 Correct 13 ms 916 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 75 ms 2288 KB Output is correct
23 Correct 70 ms 2296 KB Output is correct
24 Correct 210 ms 2384 KB Output is correct
25 Correct 279 ms 2316 KB Output is correct
26 Correct 90 ms 2288 KB Output is correct
27 Correct 1306 ms 31548 KB Output is correct
28 Correct 1571 ms 33344 KB Output is correct
29 Correct 1430 ms 32840 KB Output is correct
30 Correct 741 ms 26120 KB Output is correct
31 Execution timed out 3059 ms 117836 KB Time limit exceeded
32 Halted 0 ms 0 KB -