oj.uz

Submission #982270

# Submission time Handle Problem Language Result Execution time Memory
982270 2024-05-14T05:13:08 Z MuhammadSaram Circle selection (APIO18_circle_selection) C++17
7 / 100
 851 ms 66696 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 (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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 500 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 32 ms 604 KB Output is correct
23 Correct 30 ms 820 KB Output is correct
24 Correct 33 ms 816 KB Output is correct
25 Correct 30 ms 796 KB Output is correct
26 Correct 36 ms 636 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 66696 KB Output is correct
2 Correct 772 ms 59196 KB Output is correct
3 Correct 727 ms 60192 KB Output is correct
4 Correct 735 ms 60760 KB Output is correct
5 Incorrect 576 ms 55216 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 129 ms 18180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 463 ms 53936 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 500 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 32 ms 604 KB Output is correct
23 Correct 30 ms 820 KB Output is correct
24 Correct 33 ms 816 KB Output is correct
25 Correct 30 ms 796 KB Output is correct
26 Correct 36 ms 636 KB Output is correct
27 Incorrect 10 ms 2528 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 500 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 32 ms 604 KB Output is correct
23 Correct 30 ms 820 KB Output is correct
24 Correct 33 ms 816 KB Output is correct
25 Correct 30 ms 796 KB Output is correct
26 Correct 36 ms 636 KB Output is correct
27 Correct 851 ms 66696 KB Output is correct
28 Correct 772 ms 59196 KB Output is correct
29 Correct 727 ms 60192 KB Output is correct
30 Correct 735 ms 60760 KB Output is correct
31 Incorrect 576 ms 55216 KB Output isn't correct
32 Halted 0 ms 0 KB -