Submission #49077

#	Time	Username	Problem	Language	Result	Execution time	Memory
49077		yusufake	원 고르기 (APIO18_circle_selection)	C++98	87 / 100	3049 ms	33364 KiB

circle_selection

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

#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;
    pp mn[2];
    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]);
    root->mn[0] = mp( p[ A[l] ][0] , A[l] );
    root->mn[1] = mp( p[ B[l] ][1] , B[l] );
    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;
}

node* del(node* root, int i, int k){
    if(root == NULL) assert(0);
    if(root->id == i){
        if(root -> r != NULL){
            int j = root->r->mn[k].nd;
            root->p[0] = p[j][0]; root->p[1] = p[j][1];  root->id = j;
            root -> r = del(root->r, j, !k);
        }   
        else if(root -> l != NULL){
            int j = root->l->mn[k].nd;
            root->p[0] = p[j][0]; root->p[1] = p[j][1];  root->id = j;
            root->r = root->l;  root->l = NULL;
            root->r = del(root->r, j, !k);
        }
        else return NULL;
    }
    else{
        if(p[i][k] < root->p[k]) root->l = del(root->l, i, !k);
        else root->r = del(root->r, i, !k);
    }
    
    root->mn[k] = root->l ? root->l->mn[k] : mp( root->p[k] , root->id );
    root->mn[!k] = mp(root->p[!k],root->id);
    if(root->l != NULL) root->mn[!k] = min(root->mn[!k] , root->l->mn[!k]);
    if(root->r != NULL) root->mn[!k] = min(root->mn[!k] , root->r->mn[!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))
		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, 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:27: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:103: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