oj.uz

Submission #99830

# Submission time Handle Problem Language Result Execution time Memory
99830 2019-03-07T16:55:48 Z TadijaSebez Circle selection (APIO18_circle_selection) C++11
0 / 100
 3000 ms 50784 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
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];
unordered_map<ll,int> id;
set<pair<int,int>> all[N];
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;
		id.clear();
		int cnt=0;
		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));
			ll p=pa.first;
			if(!id[p]) id[p]=++cnt,all[cnt].clear();
			all[id[p]].insert(mp(pa.second,a[i].id));
		}
		//for(i=1;i<=cnt;i++) sort(all[i].begin(),all[i].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;
				if(!id.count(p)) continue;
				int idx=id[p];
				auto lb=all[idx].upper_bound(mp(y-3,mul));
				auto rb=all[idx].upper_bound(mp(y+2,mul));
				vector<pair<int,int>> er;
				for(auto r=lb;r!=rb;r++)
				{
					int c=r->second;
					if(sec(b[c],a[i])) ans[c]=a[i].id;
					else er.pb(*r);
				}
				for(auto p:er) all[idx].erase(p);
			}
		}
	}
	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:68: 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:35:54: 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:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:20:77: 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14464 KB Output is correct
2 Correct 17 ms 14464 KB Output is correct
3 Correct 16 ms 14464 KB Output is correct
4 Correct 17 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 16 ms 14464 KB Output is correct
7 Correct 17 ms 14556 KB Output is correct
8 Correct 14 ms 14464 KB Output is correct
9 Correct 15 ms 14592 KB Output is correct
10 Incorrect 15 ms 14464 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1144 ms 50784 KB Output is correct
2 Execution timed out 3025 ms 49676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14464 KB Output is correct
2 Correct 17 ms 14464 KB Output is correct
3 Correct 16 ms 14464 KB Output is correct
4 Correct 17 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 16 ms 14464 KB Output is correct
7 Correct 17 ms 14556 KB Output is correct
8 Correct 14 ms 14464 KB Output is correct
9 Correct 15 ms 14592 KB Output is correct
10 Incorrect 15 ms 14464 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14464 KB Output is correct
2 Correct 17 ms 14464 KB Output is correct
3 Correct 16 ms 14464 KB Output is correct
4 Correct 17 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 16 ms 14464 KB Output is correct
7 Correct 17 ms 14556 KB Output is correct
8 Correct 14 ms 14464 KB Output is correct
9 Correct 15 ms 14592 KB Output is correct
10 Incorrect 15 ms 14464 KB Output isn't correct
11 Halted 0 ms 0 KB -