Submission #272852

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
272852	2020-08-18 16:18:15	MKopchev	Circle selection (APIO18_circle_selection)	C++14	100 / 100	2391 ms	269132 KiB

circle_selection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int nmax=3e5+42,inf=1e9+42,MX=(1<<20)+42;
struct circle
{
    int x,y,r,id;
};
int n;
circle inp[nmax],sorted_inp[nmax],other_sorted[nmax];
bool touch(circle a,circle b)
{
    long long d=1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
    long long mx=a.r+b.r;
    mx=mx*mx;
    return d<=mx;
}
bool cmp(circle a,circle b)
{
    if(a.r!=b.r)return a.r>b.r;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

circle_selection.cpp: In function 'int find_first(int, int)':
circle_selection.cpp:60:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     if(start>=nodes[where].size())return -1;
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void match(int, int, int, int, int, circle)':
circle_selection.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if(start==nodes[node].size())return;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while(start<nodes[node].size()&&nodes[node][start].first<=y2)
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:126:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             if(nxt[node][k]<nodes[node].size())
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:188:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |             for(int j=0;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~
circle_selection.cpp:199:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  199 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |     ^~~
circle_selection.cpp:199:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  199 |     for(int i=1;i<=n;i++)printf("%i ",outp[i]);printf("\n");
      |                                                ^~~~~~
circle_selection.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
circle_selection.cpp:165:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  165 |         scanf("%i%i%i",&inp[i].x,&inp[i].y,&inp[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13