各种样例测试都通过了,找不到哪里能RE
我用的是DEV-C++ 5.10,不知道是不是版本问题
#include<bits/stdc++.h>
using namespace std;
struct point
{
int ind,x,y,z,rank;
long long dis;
}p[200001];
multimap<double,int> m[4];
long long l,n,cnt1=1;
bool axis_y=0;
void ins(int i)
{
if(p[i].x==0&&p[i].y==0)
{
l+=p[i].z;
p[i].rank=1;
cnt1++;
axis_y=1;
}
if(axis_y==1&&p[i].x==0&&p[i].y>0)
{
cnt1--;
axis_y=0;
}
if(p[i].x==0&&p[i].y>0)
m[0].insert(pair<double,int>(1,i));
if(p[i].x==0&&p[i].y<0)
m[2].insert(pair<double,int>(1,i));
if(p[i].x<0)
m[1].insert(pair<double,int>((double)p[i].y/p[i].x,i));
if(p[i].x>0)
m[3].insert(pair<double,int>((double)p[i].y/p[i].x,i));
}
bool cmp0(point u,point v)
{
if(u.dis<v.dis)return 1;
return 0;
}
bool cmp1(point u,point v)
{
if(u.ind<v.ind)return 1;
return 0;
}
int main()
{
cin>>n>>l;
for(int i=1;i<=n;i++)
{
cin>>p[i].x>>p[i].y>>p[i].z;
p[i].dis=(long long)(p[i].y*p[i].y+p[i].x*p[i].x);
p[i].ind=i;p[i].rank=-1;
}
sort(p+1,p+n+1,cmp0);
int i=1;
for(i=1;p[i].dis<=l*l&&i<=n;i++)
ins(i);
multimap<double,int>::iterator it[4],tmp_it;
while(!m[0].empty()||!m[1].empty()||!m[2].empty()||!m[3].empty())
{
for(int j=0;j<4;j++)
{
it[j]=m[j].begin();
while(it[j]!=m[j].end())
{
double tmp=it[j]->first;
p[it[j]->second].rank=cnt1;
l+=p[it[j]->second].z;
int cnt2=1;
for(;p[i].dis<=l*l&&i<=n;i++)
ins(i);
tmp_it=m[j].end();tmp_it--;
m[j].erase(it[j]);
if(tmp_it==it[j])
it[j]=m[j].end();
else
it[j]++;
while(it[j]!=m[j].end()&&it[j]->first==tmp)
{
p[it[j]->second].rank=cnt1;
l+=p[it[j]->second].z;
for(;p[i].dis<=l*l&&i<=n;i++)
ins(i);
tmp_it=m[j].end();tmp_it--;
m[j].erase(it[j]);
if(tmp_it==it[j])
it[j]=m[j].end();
else
it[j]++;
cnt2++;
}
cnt1+=cnt2;
}
}
}
sort(p+1,p+n+1,cmp1);
for(i=1;i<=n;i++)
cout<<p[i].rank<<' ';
}