Submission #134929

# Submission time Handle Problem Language Result Execution time Memory
134929 2019-07-23T12:22:25 Z Lawliet Circle selection (APIO18_circle_selection) C++14
0 / 100
329 ms 19796 KB
#include <bits/stdc++.h>

#define MAX 5010
#define R first.first
#define X second.first
#define Y second.second

using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> circle;

int n;

int removed[MAX];

lli n1, n2, n3;

vector<circle> v;

bool intersect(int i, int j)
{
	lli sR = v[i].R + v[j].R; sR = -sR;
	lli dX = v[i].X - v[j].X;
	lli dY = v[i].Y - v[j].Y;

	return (dX*dX <= (sR + dY)*(sR - dY));
}

int main()
{
	scanf("%d",&n);

	memset(removed , -1 , sizeof(removed));

	for(int g = 1 ; g <= n ; g++)
	{
		scanf("%lld %lld %lld",&n1,&n2,&n3);

		circle k;

		k = {{-n3 , g} , {n1 , n2}};

		v.push_back( k );
	}	

	sort(v.begin() , v.end());

	for(int g = 0 ; g < n ; g++)
	{
		int curInd = v[g].first.second;

		if(removed[curInd] != -1) continue;

		for(int h = g ; h < n ; h++)
		{
			if(intersect(g , h))
			{
				int ind = v[h].first.second;

				removed[ind] = curInd;
			}
		}
	}

	for(int g = 1 ; g <= n ; g++)
		printf("%d ",removed[g]);
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&n1,&n2,&n3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 185 ms 19796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 70 ms 7004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 329 ms 19788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -