답안 #77971 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77971	2018-10-01T14:13:23 Z	autumn_eel	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	859 ms	37428 KB

circle_selection

#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	double minx=inf,miny=inf,maxx=-inf,maxy=-inf;
	for(int i=l;i<r+1;i++){
		minx=min(minx,a[i].x-a[i].r);
		miny=min(miny,a[i].y-a[i].r);
		maxx=max(maxx,a[i].x+a[i].r);
		maxy=max(maxy,a[i].y+a[i].r);
	}
	if(maxx-minx>maxy-miny)k=0;
	else k=1;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x,y,r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}
/*
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef double db;
using namespace std;
 
const int N=300010;
const db inf=1e20,eps=1e-3,alpha=acos(-1)/3;
int n,rt,ans[N];
db x,y,r;
struct P{ db x,y,r; int id; }cur,a[N];
struct Tr{ int ls,rs; db x1,y1,x2,y2; P c; }T[N];
 
bool cmpx(const P &a,const P &b){ return a.x<b.x; }
bool cmpy(const P &a,const P &b){ return a.y<b.y; }
bool cmpr(const P &a,const P &b){ return (a.r==b.r) ? a.id<b.id : a.r>b.r; }
 
void F(int x,int y){
	T[x].x1=min(T[x].x1,T[y].x1); T[x].x2=max(T[x].x2,T[y].x2);
	T[x].y1=min(T[x].y1,T[y].y1); T[x].y2=max(T[x].y2,T[y].y2);
}
 
void upd(int x){
	if (ans[T[x].c.id]) T[x].x1=T[x].y1=inf,T[x].x2=T[x].y2=-inf;
	else{
		T[x].x1=T[x].c.x-T[x].c.r; T[x].x2=T[x].c.x+T[x].c.r;
		T[x].y1=T[x].c.y-T[x].c.r; T[x].y2=T[x].c.y+T[x].c.r;
	}
	if (T[x].ls) F(x,T[x].ls);
	if (T[x].rs) F(x,T[x].rs);
}
 
int build(int l,int r,int k){
	if (l>r) return 0;
	int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,k?cmpy:cmpx);
	T[mid].c=a[mid];
	T[mid].ls=build(l,mid-1,k^1); T[mid].rs=build(mid+1,r,k^1);
	upd(mid); return mid;
}
 
db sqr(db x){ return x*x; }
bool Out(int x){ return (T[x].x2<cur.x-cur.r-eps) || (T[x].x1>cur.x+cur.r+eps) || (T[x].y2<cur.y-cur.r-eps) || (T[x].y1>cur.y+cur.r+eps); }
bool chk(P &a){ return sqr(a.x-cur.x)+sqr(a.y-cur.y)<=sqr(a.r+cur.r)+eps; }
 
void que(int x){
	if (Out(x)) return;
	if (!ans[T[x].c.id] && chk(T[x].c)) ans[T[x].c.id]=cur.id;
	if (T[x].ls) que(T[x].ls);
	if (T[x].rs) que(T[x].rs);
}
 
int main(){
	//~ freopen("apiob.in","r",stdin);
	//~ freopen("apiob.out","w",stdout);
	scanf("%d",&n);
	rep(i,1,n)
		scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x*cos(alpha)+y*sin(alpha),y*cos(alpha)-x*sin(alpha),r,i};
	rt=build(1,n,0); sort(a+1,a+n+1,cmpr);
	rep(i,1,n) if (!ans[a[i].id]) ans[a[i].id]=a[i].id,cur=a[i],que(rt);
	rep(i,1,n) printf("%d ",ans[i]); puts("");
	return 0;
}*/

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:4:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
                    ^
circle_selection.cpp:70:2: note: in expansion of macro 'rep'
  rep(i,1,n) printf("%d ",ans[i]); puts("");
  ^~~
circle_selection.cpp:70:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  rep(i,1,n) printf("%d ",ans[i]); puts("");
                                   ^~~~
circle_selection.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:67:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf%lf",&x,&y,&r),a[i]=(P){x,y,r,i};
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	536 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	2 ms	548 KB	Output is correct
9	Correct	2 ms	680 KB	Output is correct
10	Correct	2 ms	680 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	2 ms	748 KB	Output is correct
13	Correct	2 ms	748 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	2 ms	748 KB	Output is correct
16	Correct	4 ms	748 KB	Output is correct
17	Correct	3 ms	748 KB	Output is correct
18	Correct	3 ms	888 KB	Output is correct
19	Correct	7 ms	1432 KB	Output is correct
20	Correct	8 ms	1584 KB	Output is correct
21	Correct	10 ms	1752 KB	Output is correct
22	Correct	9 ms	1860 KB	Output is correct
23	Correct	13 ms	1928 KB	Output is correct
24	Correct	9 ms	1976 KB	Output is correct
25	Correct	9 ms	1976 KB	Output is correct
26	Correct	14 ms	1976 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	365 ms	35260 KB	Output is correct
2	Correct	343 ms	35400 KB	Output is correct
3	Correct	330 ms	35400 KB	Output is correct
4	Correct	341 ms	35420 KB	Output is correct
5	Correct	344 ms	35420 KB	Output is correct
6	Correct	419 ms	35420 KB	Output is correct
7	Correct	372 ms	35560 KB	Output is correct
8	Correct	376 ms	35560 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	35560 KB	Output is correct
2	Correct	197 ms	35560 KB	Output is correct
3	Correct	761 ms	35600 KB	Output is correct
4	Correct	756 ms	35600 KB	Output is correct
5	Correct	655 ms	35600 KB	Output is correct
6	Correct	277 ms	35600 KB	Output is correct
7	Correct	135 ms	35600 KB	Output is correct
8	Correct	26 ms	35600 KB	Output is correct
9	Correct	741 ms	35600 KB	Output is correct
10	Correct	596 ms	35600 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	738 ms	35600 KB	Output is correct
2	Correct	736 ms	35600 KB	Output is correct
3	Correct	491 ms	35600 KB	Output is correct
4	Correct	701 ms	36288 KB	Output is correct
5	Correct	776 ms	36304 KB	Output is correct
6	Correct	463 ms	36304 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	536 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	2 ms	548 KB	Output is correct
9	Correct	2 ms	680 KB	Output is correct
10	Correct	2 ms	680 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	2 ms	748 KB	Output is correct
13	Correct	2 ms	748 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	2 ms	748 KB	Output is correct
16	Correct	4 ms	748 KB	Output is correct
17	Correct	3 ms	748 KB	Output is correct
18	Correct	3 ms	888 KB	Output is correct
19	Correct	7 ms	1432 KB	Output is correct
20	Correct	8 ms	1584 KB	Output is correct
21	Correct	10 ms	1752 KB	Output is correct
22	Correct	9 ms	1860 KB	Output is correct
23	Correct	13 ms	1928 KB	Output is correct
24	Correct	9 ms	1976 KB	Output is correct
25	Correct	9 ms	1976 KB	Output is correct
26	Correct	14 ms	1976 KB	Output is correct
27	Correct	15 ms	36304 KB	Output is correct
28	Correct	14 ms	36304 KB	Output is correct
29	Correct	14 ms	36304 KB	Output is correct
30	Correct	17 ms	36304 KB	Output is correct
31	Correct	17 ms	36304 KB	Output is correct
32	Correct	18 ms	36304 KB	Output is correct
33	Correct	130 ms	36304 KB	Output is correct
34	Correct	130 ms	36304 KB	Output is correct
35	Correct	181 ms	36304 KB	Output is correct
36	Correct	199 ms	36304 KB	Output is correct
37	Correct	196 ms	36304 KB	Output is correct
38	Correct	194 ms	36304 KB	Output is correct
39	Correct	199 ms	36304 KB	Output is correct
40	Correct	196 ms	36304 KB	Output is correct
41	Correct	196 ms	36304 KB	Output is correct
42	Correct	152 ms	36304 KB	Output is correct
43	Correct	169 ms	36304 KB	Output is correct
44	Correct	204 ms	36304 KB	Output is correct
45	Correct	176 ms	36304 KB	Output is correct
46	Correct	288 ms	36304 KB	Output is correct
47	Correct	184 ms	36304 KB	Output is correct
48	Correct	178 ms	36304 KB	Output is correct
49	Correct	184 ms	36304 KB	Output is correct
50	Correct	171 ms	36304 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	536 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	2 ms	548 KB	Output is correct
9	Correct	2 ms	680 KB	Output is correct
10	Correct	2 ms	680 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	2 ms	748 KB	Output is correct
13	Correct	2 ms	748 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Correct	2 ms	748 KB	Output is correct
16	Correct	4 ms	748 KB	Output is correct
17	Correct	3 ms	748 KB	Output is correct
18	Correct	3 ms	888 KB	Output is correct
19	Correct	7 ms	1432 KB	Output is correct
20	Correct	8 ms	1584 KB	Output is correct
21	Correct	10 ms	1752 KB	Output is correct
22	Correct	9 ms	1860 KB	Output is correct
23	Correct	13 ms	1928 KB	Output is correct
24	Correct	9 ms	1976 KB	Output is correct
25	Correct	9 ms	1976 KB	Output is correct
26	Correct	14 ms	1976 KB	Output is correct
27	Correct	365 ms	35260 KB	Output is correct
28	Correct	343 ms	35400 KB	Output is correct
29	Correct	330 ms	35400 KB	Output is correct
30	Correct	341 ms	35420 KB	Output is correct
31	Correct	344 ms	35420 KB	Output is correct
32	Correct	419 ms	35420 KB	Output is correct
33	Correct	372 ms	35560 KB	Output is correct
34	Correct	376 ms	35560 KB	Output is correct
35	Correct	2 ms	35560 KB	Output is correct
36	Correct	197 ms	35560 KB	Output is correct
37	Correct	761 ms	35600 KB	Output is correct
38	Correct	756 ms	35600 KB	Output is correct
39	Correct	655 ms	35600 KB	Output is correct
40	Correct	277 ms	35600 KB	Output is correct
41	Correct	135 ms	35600 KB	Output is correct
42	Correct	26 ms	35600 KB	Output is correct
43	Correct	741 ms	35600 KB	Output is correct
44	Correct	596 ms	35600 KB	Output is correct
45	Correct	738 ms	35600 KB	Output is correct
46	Correct	736 ms	35600 KB	Output is correct
47	Correct	491 ms	35600 KB	Output is correct
48	Correct	701 ms	36288 KB	Output is correct
49	Correct	776 ms	36304 KB	Output is correct
50	Correct	463 ms	36304 KB	Output is correct
51	Correct	15 ms	36304 KB	Output is correct
52	Correct	14 ms	36304 KB	Output is correct
53	Correct	14 ms	36304 KB	Output is correct
54	Correct	17 ms	36304 KB	Output is correct
55	Correct	17 ms	36304 KB	Output is correct
56	Correct	18 ms	36304 KB	Output is correct
57	Correct	130 ms	36304 KB	Output is correct
58	Correct	130 ms	36304 KB	Output is correct
59	Correct	181 ms	36304 KB	Output is correct
60	Correct	199 ms	36304 KB	Output is correct
61	Correct	196 ms	36304 KB	Output is correct
62	Correct	194 ms	36304 KB	Output is correct
63	Correct	199 ms	36304 KB	Output is correct
64	Correct	196 ms	36304 KB	Output is correct
65	Correct	196 ms	36304 KB	Output is correct
66	Correct	152 ms	36304 KB	Output is correct
67	Correct	169 ms	36304 KB	Output is correct
68	Correct	204 ms	36304 KB	Output is correct
69	Correct	176 ms	36304 KB	Output is correct
70	Correct	288 ms	36304 KB	Output is correct
71	Correct	184 ms	36304 KB	Output is correct
72	Correct	178 ms	36304 KB	Output is correct
73	Correct	184 ms	36304 KB	Output is correct
74	Correct	171 ms	36304 KB	Output is correct
75	Correct	781 ms	36304 KB	Output is correct
76	Correct	402 ms	36344 KB	Output is correct
77	Correct	392 ms	36412 KB	Output is correct
78	Correct	409 ms	36412 KB	Output is correct
79	Correct	616 ms	36420 KB	Output is correct
80	Correct	421 ms	36420 KB	Output is correct
81	Correct	791 ms	36420 KB	Output is correct
82	Correct	796 ms	36420 KB	Output is correct
83	Correct	859 ms	36420 KB	Output is correct
84	Correct	733 ms	36420 KB	Output is correct
85	Correct	698 ms	36420 KB	Output is correct
86	Correct	750 ms	36420 KB	Output is correct
87	Correct	755 ms	36472 KB	Output is correct
88	Correct	738 ms	36472 KB	Output is correct
89	Correct	765 ms	36472 KB	Output is correct
90	Correct	692 ms	36472 KB	Output is correct
91	Correct	723 ms	36472 KB	Output is correct
92	Correct	774 ms	36472 KB	Output is correct
93	Correct	666 ms	36472 KB	Output is correct
94	Correct	660 ms	36472 KB	Output is correct
95	Correct	700 ms	36488 KB	Output is correct
96	Correct	615 ms	36488 KB	Output is correct
97	Correct	680 ms	36524 KB	Output is correct
98	Correct	517 ms	36560 KB	Output is correct
99	Correct	706 ms	36620 KB	Output is correct
100	Correct	671 ms	36620 KB	Output is correct
101	Correct	579 ms	36620 KB	Output is correct
102	Correct	621 ms	37304 KB	Output is correct
103	Correct	640 ms	37304 KB	Output is correct
104	Correct	651 ms	37304 KB	Output is correct
105	Correct	539 ms	37304 KB	Output is correct
106	Correct	597 ms	37304 KB	Output is correct
107	Correct	596 ms	37428 KB	Output is correct
108	Correct	638 ms	37428 KB	Output is correct
109	Correct	636 ms	37428 KB	Output is correct
110	Correct	599 ms	37428 KB	Output is correct
111	Correct	604 ms	37428 KB	Output is correct
112	Correct	621 ms	37428 KB	Output is correct
113	Correct	609 ms	37428 KB	Output is correct
114	Correct	597 ms	37428 KB	Output is correct
115	Correct	583 ms	37428 KB	Output is correct
116	Correct	580 ms	37428 KB	Output is correct

답안 #77971

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 15.0 / 15.0

Subtask #4 23.0 / 23.0

Subtask #5 30.0 / 30.0

Subtask #6 13.0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
15.0 / 15.0

Subtask #4
23.0 / 23.0

Subtask #5
30.0 / 30.0

Subtask #6
13.0 / 13.0