oj.uz

Submission #110184

# Submission time Handle Problem Language Result Execution time Memory
110184 2019-05-10T02:37:29 Z baluteshih Circle selection (APIO18_circle_selection) C++14
12 / 100
 1029 ms 49292 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll ans[300005],x[300005],y[300005],r[300005],arr[300005],rmax=0;
vector<vector<vector<ll>>> v;
vector<vector<ll>> sigy;
vector<ll> sigx;

bool yee(ll a,ll b)
{
	if(x[a]==x[b]) return y[a]<y[b];
	return x[a]<x[b];
}

bool yee2(ll a,ll b)
{
	if(r[a]==r[b]) return a<b;
	return r[a]>r[b];
}

bool intersect(ll a,ll b)
{
	return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])<=(r[a]+r[b])*(r[a]+r[b]);
}

ll blk(ll x)
{
	if(x>0) return x/rmax;
	return x/rmax-1;
}

void rebuild()
{
	vector<vector<vector<ll>>> tmp;
	vector<ll>().swap(sigx),vector<vector<ll>>().swap(sigy);
	for(auto xv:v)
		for(auto yv:xv)
			for(auto c:yv)
				if(tmp.empty()||sigx.back()!=blk(x[c]))
					tmp.pb(vector<vector<ll>>(1,vector<ll>(1,c))),sigx.pb(blk(x[c])),sigy.pb(vector<ll>(1,blk(y[c])));
				else
					if(sigy.back().back()==blk(y[c])) tmp.back().back().pb(c);
					else tmp.back().pb(vector<ll>(1,c)),sigy.back().pb(blk(y[c]));
	v.swap(tmp);
}

int main()
{jizz
	ll n;
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> x[i] >> y[i] >> r[i],arr[i]=i,rmax=max(rmax,r[i]);
	sort(arr+1,arr+n+1,yee);
	for(int i=1;i<=n;++i)
		if(v.empty()||sigx.back()!=blk(x[arr[i]]))
			v.pb(vector<vector<ll>>(1,vector<ll>(1,arr[i]))),sigx.pb(blk(x[arr[i]])),sigy.pb(vector<ll>(1,blk(y[arr[i]])));
		else
			if(sigy.back().back()==blk(y[arr[i]])) v.back().back().pb(arr[i]);
			else v.back().pb(vector<ll>(1,arr[i])),sigy.back().pb(blk(y[arr[i]]));
	sort(arr+1,arr+n+1,yee2);
	for(int i=1;i<=n;++i)
	{
		int cur=arr[i];
		if(ans[cur]) continue;
		if(r[cur]*2<=rmax)
			rmax=r[cur],rebuild();
		int L=0,R=(int)v.size()-1;
		while(L<R)
		{
			int m=L+R>>1;
			if(sigx[m]+2>=blk(x[cur])) R=m;
			else L=m+1;
		}
		for(int j=L;j<v.size()&&sigx[j]<=blk(x[cur])+2;++j)
		{
			int l=0,r=(int)v[j].size()-1;
			while(l<r)
			{
				int m=l+r>>1;
				if(sigy[j][m]+2>=blk(y[cur])) r=m;
				else l=m+1;
			}
			for(int k=l;k<v[j].size()&&sigy[j][k]<=blk(y[cur])+2;++k)
			{
				vector<ll> tmp;
				for(auto p:v[j][k])
					if(intersect(p,cur)) ans[p]=cur;
					else tmp.pb(p);
				v[j][k].swap(tmp);
			}
		}
	}
	for(int i=1;i<=n;++i)
		cout << ans[i] << " \n"[i==n];
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:83:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m=L+R>>1;
          ~^~
circle_selection.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=L;j<v.size()&&sigx[j]<=blk(x[cur])+2;++j)
               ~^~~~~~~~~
circle_selection.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=l+r>>1;
           ~^~
circle_selection.cpp:96:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=l;k<v[j].size()&&sigy[j][k]<=blk(y[cur])+2;++k)
                ~^~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 432 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Incorrect 3 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 22868 KB Output is correct
2 Correct 300 ms 21696 KB Output is correct
3 Correct 354 ms 21988 KB Output is correct
4 Correct 296 ms 21456 KB Output is correct
5 Correct 303 ms 22776 KB Output is correct
6 Correct 712 ms 39440 KB Output is correct
7 Correct 321 ms 24392 KB Output is correct
8 Correct 363 ms 26336 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 432 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Incorrect 3 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 432 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Incorrect 3 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -