oj.uz

답안 #64361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64361 2018-08-04T08:33:39 Z zscoder 원 고르기 (APIO18_circle_selection) C++17
0 / 100
 3000 ms 53560 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct circle
{
	int x,y,r,id;
	circle(int _x, int _y, int _r, int _id){x=_x;y=_y;r=_r;id=_id;}
};

bool operator<(circle a, circle b)
{
	if(a.r!=b.r) return a.r<b.r;
	else return a.id>b.id;
}

int ans[333333];
vector<circle> vec;
map<ii,vector<circle> > ma;

void init(int R)
{
	ma.clear();
	for(int i=0;i<vec.size();i++)
	{
		if(!ans[vec[i].id])
		{
			ma[mp(vec[i].x/R, vec[i].y/R)].pb(vec[i]);
		}
	}
}

bool intersect(circle x, circle y)
{
	ll d = (x.x-y.x)*1LL*(x.x-y.x) + (x.y-y.y)*1LL*(x.y-y.y);
	return (d<=(x.r+y.r)*1LL*(x.r+y.r));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n; 
	for(int i=0;i<n;i++)
	{
		int x,y,r; cin>>x>>y>>r;
		vec.pb(circle(x,y,r,i+1));
	}
	sort(vec.rbegin(),vec.rend());
	int curC = int(1e9); init(curC);
	for(int i=0;i<vec.size();i++)
	{
		if(ans[vec[i].id]) continue;
		cerr<<vec[i].id<<'\n';
		while(vec[i].r*2<curC)
		{
			curC/=2; init(curC);
		}
		int x=vec[i].x/curC; int y=vec[i].y/curC;
		for(int dx=-2;dx<=2;dx++)
		{
			for(int dy=-2;dy<=2;dy++)
			{
				int x2=x+dx; int y2=y+dy;
				if(ma.find(mp(x2,y2))==ma.end()) continue;
				for(auto it = ma[mp(x2,y2)].begin(); it != ma[mp(x2,y2)].end();)
				{
					if(intersect(*it, vec[i]))
					{
						ans[it->id] = vec[i].id;
						it = ma[mp(x2,y2)].erase(it);
					}
					else
					{
						it++;
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i];
		if(i+1<=n) cout<<' ';
	}
	cout<<'\n';
}

Compilation message

circle_selection.cpp: In function 'void init(int)':
circle_selection.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3037 ms 26252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 26252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3022 ms 53560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -