Submission #982270

#	Time	Username	Problem	Language	Result	Execution time	Memory
982270		MuhammadSaram	Circle selection (APIO18_circle_selection)	C++17	7 / 100	851 ms	66696 KiB

circle_selection

/********************* بسم الله الرحمن الرحيم ***********************/
 /******************** ٱلْحَمْدُ لِلَّٰهِ رَبِّ ٱلْعَالَمِينَ *************************/
/******************* Prophet Muhammad صلى الله عليه وسلم ************/
   /*********************** وَقُل رَّبِّ زِدْنِي عِلْمًا **************************/

#ifdef ONLINE_JUDGE
	#pragma GCC optimize("Ofast")
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#else

#endif

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define in binary_search
#define ll long long
#define ld long double
#define Hey ios::sync_with_stdio(false);
#define Welcome cin.tie(NULL), cout.tie(NULL);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()

int dis2(pair<int,int> p,pair<int,int> p1)
{
	return (p.first-p1.first)*(p.first-p1.first)+(p.second-p1.second)*(p.second-p1.second);
}

void solve()
{
	int n;
	cin>>n;
	int x[n],y[n],r[n],ans[n];
	vector<pair<int,int>> cir;
	for (int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i]>>r[i];
		cir.push_back({-r[i],i});
		ans[i]=i;
	}
	sort(all(cir));
	if (n<=5000)
	{
		for (int j=0;j<n;j++)
		{
			int i=cir[j].second;
			if (ans[i]!=i)
				continue;
			for (int k=j+1;k<n;k++)
			{
				if (ans[cir[k].second]==cir[k].second and dis2({x[i],y[i]},{x[cir[k].second],y[cir[k].second]})<=(r[i]+r[cir[k].second])*(r[i]+r[cir[k].second]))
					ans[cir[k].second]=i;
			}
		}
	}
	else
	{
		set<pair<int,int>> se,se1;
		for (int i=0;i<n;i++)
		{
			se.insert({x[i]-r[i],i});
			se1.insert({x[i]+r[i],i});
		}
		for (int j=0;j<n;j++)
		{
			int i=cir[j].second;
			if (ans[i]!=i)
				continue;
			se.erase({x[i]-r[i],i});
			se1.erase({x[i]+r[i],i});
			auto a=se.lower_bound({x[i]-r[i],0});
			auto b=se.upper_bound({x[i]+r[i],0});
			vector<pair<int,int>> v;
			while (a!=b)
			{
				int k=(*a).second;
				ans[k]=i;
				se1.erase({x[k]+r[k],k});
				v.push_back((*a));
				a++;
			}
			for (auto xe:v)
				se.erase(xe);
			a=se1.lower_bound({x[i]-r[i],0});
			b=se1.upper_bound({x[i]+r[i],0});
			v.clear();
			while (a!=b)
			{
				int k=(*a).second;
				ans[k]=i;
				se.erase({x[k]-r[k],k});
				v.push_back((*a));
				a++;
			}
			for (auto xe:v)
				se1.erase(xe);
		}
	}
	for (int i=0;i<n;i++)
		cout<<ans[i]+1<<' ';
	cout<<endl;
}

signed main()
{
	Hey! Welcome // S'up
	
	int t = 1;
	cout<<fixed<<setprecision(20);
	while (t--)
		solve();
	
	return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:109:5: warning: value computed is not used [-Wunused-value]
  109 |  Hey! Welcome // S'up
      |     ^

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