oj.uz

Submission #199457

# Submission time Handle Problem Language Result Execution time Memory
199457 2020-02-01T12:54:40 Z TadijaSebez Countries (BOI06_countries) C++11
100 / 100
 10 ms 428 KB 
#include <bits/stdc++.h>
using namespace std;
#define ldb long double
#define ll long long
const int N=1005;
int x[N],y[N],s[N],id[N];
int my[N];
ll sq(ll x, ll y){ return x*x+y*y;}
ll dist(int i, int j){ return sq(x[i]-x[j],y[i]-y[j]);}
bool d[N];
int main()
{
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i %i %i",&x[i],&y[i],&s[i]),id[i]=i;
	sort(id+1,id+1+n,[&](int i, int j){ return s[i]>s[j];});
	for(int j=1;j<=n;j++)
	{
		int i=id[j];
		ldb mx=0;
		int cnt=0,cap=-1;
		for(int k=1;k<=n;k++) if(k!=i)
		{
			ldb tmp=(ldb)s[k]/dist(i,k);
			if(tmp>s[i])
			{
				if(mx<tmp) mx=tmp,cnt=0;
				if(mx==tmp) cnt++,cap=my[k];
			}
		}
		if(cnt==0) my[i]=i;
		else if(cnt==1) my[i]=cap;
		else my[i]=i,d[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(my[i]==i)
		{
			if(d[i]) printf("D\n");
			else printf("K\n");
		}
		else printf("%i\n",my[i]);
	}
	return 0;
}

Compilation message

countries.cpp: In function 'int main()':
countries.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
countries.cpp:15:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i %i",&x[i],&y[i],&s[i]),id[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 8 ms 376 KB Output is correct
9 Correct 10 ms 376 KB Output is correct
10 Correct 10 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 1 ms 376 KB Output is correct
16 Correct 6 ms 376 KB Output is correct
17 Correct 7 ms 376 KB Output is correct
18 Correct 8 ms 376 KB Output is correct
19 Correct 9 ms 428 KB Output is correct
20 Correct 9 ms 376 KB Output is correct