oj.uz

Submission #982251

# Submission time Handle Problem Language Result Execution time Memory
982251 2024-05-14T04:48:35 Z MuhammadSaram Circle selection (APIO18_circle_selection) C++17
0 / 100
 1105 ms 90264 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 90264 KB Output is correct
2 Correct 1073 ms 81404 KB Output is correct
3 Correct 1082 ms 89644 KB Output is correct
4 Correct 1105 ms 89128 KB Output is correct
5 Incorrect 733 ms 79156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 192 ms 24448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -