Submission #49076

#	Time	Username	Problem	Language	Result	Execution time	Memory
49076		yusufake	Circle selection (APIO18_circle_selection)	C++98	87 / 100	3037 ms	28756 KiB

circle_selection

#include<bits/stdc++.h> 
using namespace std; 

#define _   int v, int tl, int tr, int l, int r, ll x
#define tm  (tl + tr >> 1)
#define sol v+v,tl,tm,l,r,x 
#define sag v+v+1,tm+1,tr,l,r,x

#define mp make_pair 
#define pb push_back 
#define st first 
#define nd second 

typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 3e5 + 5; 

struct node{
    int p[2],id;
    node *l, *r;
    node(int a[], int i) { l = r = NULL; p[0] = a[0]; p[1] = a[1]; id = i; }
};

int p[N][2],A[N],B[N],tmp[N],R[N],ans[N],r;
node* bld(int l, int r, int k){
    if(l > r) return NULL;
    int *X = k ? B : A;
    int *Y = k ? A : B;
    int i,j,jj, m = l+r >> 1;
    int mid = p[ X[m] ][k];
    for(; m>l && mid == p[ X[m-1] ][k] ; m--);
    node *root = new node(p[ X[m] ] , X[m]);
    for(j=l-1,jj=m,i=l;i<=r;i++){
        if(p[ Y[i] ][k] < mid)
            tmp[++j] = Y[i];
        else if(Y[i] != X[m])
            tmp[++jj] = Y[i];
    }
    for(i=l;i<=r;i++) Y[i] = tmp[i]; 
    root -> l = bld(l,m-1,!k);
    root -> r = bld(m+1,r,!k);
    return root;
}

vector < int > era;
void f(node* root, int p[], int k){
	if(root == NULL) return;
	ll a1 = root->p[0];
	ll b1 = root->p[1];
	ll a2 = p[0];
	ll b2 = p[1];
    ll c = R[ root->id ];
	if((a1-a2)*(a1-a2) + (b1-b2)*(b1-b2) <= (r+c)*(r+c) && !ans[ root->id ])
		era.pb(root->id);
	if(p[k] < root->p[k]){
		f(root->l,p,!k);
		if(root->p[k] - p[k] <= r+r) f(root->r,p,!k); 
	}
	else{
		f(root->r,p,!k);
		if(p[k] - root->p[k] <= r+r) f(root->l,p,!k); 
	}
}

int h;
bool cmp(int i, int j){
    return p[i][h] < p[j][h];
}

int n,i,j;
pp T[N];
int main()
{
    cin >> n;
    for(i=1;i<=n;i++) { scanf("%d%d%d",&p[i][0],&p[i][1],&R[i]); A[i] = B[i] = i; }
    h=0; sort(A+1,A+n+1,cmp);
    h=1; sort(B+1,B+n+1,cmp);
    node *root = bld(1,n,0);

    for(i=1;i<=n;i++) T[i] = mp(-R[i] , i);
    sort(T+1 , T+n+1);
    for(i=1;i<=n;i++){
        int id = T[i].nd;
        if(ans[id]) continue;
        era.clear();
        r = R[id];
   		f(root , p[id], 0);
   		for(auto j : era){
   			ans[j] = id;
            //root = del(root , p[era[j]] , 0);
        }
    }

    for(i=1;i<=n;i++) printf("%d ", ans[i]);
    return 0;
}    

Compilation message (stderr)

circle_selection.cpp: In function 'node* bld(int, int, int)':
circle_selection.cpp:30:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int i,j,jj, m = l+r >> 1;
                     ~^~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:76:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) { scanf("%d%d%d",&p[i][0],&p[i][1],&R[i]); A[i] = B[i] = i; }
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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