제출 #982252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982252		MuhammadSaram	원 고르기 (APIO18_circle_selection)	C++17	0 / 100	1110 ms	92060 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 (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<vector<int>> se,se1;
		for (int i=0;i<n;i++)
		{
			se.insert({x[i]-r[i],x[i]+r[i],i});
			se1.insert({x[i]+r[i],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],x[i]+r[i],i});
			se1.erase({x[i]+r[i],x[i]-r[i],i});
			auto a=se.lower_bound({x[i]-r[i],0,0});
			auto b=se.upper_bound({x[i]+r[i],0,0});
			vector<vector<int>> v;
			while (a!=b)
			{
				ans[(*a)[2]]=i;
				se1.erase({(*a)[1],(*a)[0],(*a)[2]});
				v.push_back((*a));
				a++;
			}
			for (auto xe:v)
				se.erase(xe);
			a=se1.lower_bound({x[i]-r[i],0,0});
			b=se1.upper_bound({x[i]+r[i],0,0});
			v.clear();
			while (a!=b)
			{
				ans[(*a)[2]]=i;
				se.erase({(*a)[1],(*a)[0],(*a)[2]});
				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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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