oj.uz

답안 #982252

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982252 2024-05-14T04:50:00 Z MuhammadSaram 원 고르기 (APIO18_circle_selection) C++17
0 / 100
 1110 ms 92060 KB 
/********************* بسم الله الرحمن الرحيم ***********************/
 /******************** ٱلْحَمْدُ لِلَّٰهِ رَبِّ ٱلْعَالَمِينَ *************************/
/******************* 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;
}

Compilation message

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.0

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

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1110 ms 92060 KB Output is correct
2 Correct 1074 ms 82540 KB Output is correct
3 Correct 1049 ms 82252 KB Output is correct
4 Correct 1043 ms 82012 KB Output is correct
5 Incorrect 739 ms 73396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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