oj.uz

Submission #54107

# Submission time Handle Problem Language Result Execution time Memory
54107 2018-07-02T11:20:03 Z Bodo171 Circle selection (APIO18_circle_selection) C++14
19 / 100
 1318 ms 41612 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>
using namespace std;
const int nmax=300005;
pair<int,int>  v[nmax];
set< pair<int,int> > s;
set< pair<int,int> >::iterator it1,it2;
long long x[nmax],y[nmax],r[nmax];
int vv[nmax],pp[nmax];
int tt[nmax];
int n,i,j,ind;
struct event
{
    int val,wh,tip;
}ev[3*nmax];
bool ok(int A,int B)
{
    return (1LL*(x[A]-x[B])*(x[A]-x[B])+1LL*(y[A]-y[B])*(y[A]-y[B])<=1LL*(r[A]+r[B])*(r[A]+r[B]));
}
bool comp(pair<int,int> unu,pair<int,int> doi)
{
    if(unu.first==doi.first) return unu.second<doi.second;
    return unu.first>doi.first;
}
bool Cev(event unu,event doi)
{
    if(unu.val==doi.val) return unu.tip<doi.tip;
    return unu.val<doi.val;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n;
    bool zr=1;
    for(i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i]>>r[i];
        v[i].first=r[i];
        v[i].second=i;
        if(y[i]!=0)
        {
            zr=0;
        }
    }
    if(n<=5000)
    {
        sort(v+1,v+n+1,comp);
        for(i=1;i<=n;i++)
            if(!tt[v[i].second])
        {
            tt[v[i].second]=v[i].second;
            for(j=i+1;j<=n;j++)
            {
                if(ok(v[i].second,v[j].second)&&(!tt[v[j].second]))
                    tt[v[j].second]=v[i].second;
            }
        }
        for(i=1;i<=n;i++)
            cout<<tt[i]<<' ';
        return 0;
    }
    if(zr)
    {
        int cap1,cap2;
        sort(v+1,v+n+1,comp);
        for(i=1;i<=n;i++)
        {
            cap1=x[i]-r[i];cap2=x[i]+r[i];
            s.insert({cap1,i});
            s.insert({cap2,i});
        }
        bool ok;
        for(i=1;i<=n;i++)
            if(!tt[v[i].second])
        {
            ind=v[i].second;tt[ind]=ind;
            cap1=x[ind]-r[ind];
            it1=s.lower_bound({cap1,0});ok=1;
            while((!s.empty())&&ok&&it1!=s.end())
            {
                it2=it1;it2++;
                if((*it1).first<=x[ind]+r[ind]&&(!tt[(*it1).second]))
                {
                    tt[(*it1).second]=ind;
                }
                s.erase(it1);
                if(it2==s.end()||((*it2).first>x[ind]+r[ind]))
                    ok=0;
                it1=it2;
            }
        }
        for(i=1;i<=n;i++)
            cout<<tt[i]<<' ';
        return 0;
    }
    int X,nr=0;
    for(i=1;i<=n;i++)
    {
        X=x[i];
        ev[++nr]={x[i]-r[i],i,1};
        ev[++nr]={x[i]+r[i]+1,i,-1};
    }
    sort(ev+1,ev+nr+1,Cev);
    for(i=1;i<=n;i++)
        vv[i]=y[i];
    for(i=1;i<=nr;i++)
    {
        if(ev[i].tip==-1)
        {
            s.erase({vv[ev[i].wh],ev[i].wh});
        }
        if(ev[i].tip==1)
        {
            if(!s.empty())
            {
                it1=s.lower_bound({vv[ev[i].wh],0});
                if(it1!=s.end())
                {
                    ind=(*it1).second;
                    if(ok(ev[i].wh,ind)) pp[ev[i].wh]=ind,pp[ind]=ev[i].wh;
                }
                if(it1!=s.begin())
                {
                    it1--;
                    ind=(*it1).second;
                    if(ok(ev[i].wh,ind)) pp[ev[i].wh]=ind,pp[ind]=ev[i].wh;
                }
            }
            s.insert({vv[ev[i].wh],ev[i].wh});
        }
    }
    for(i=1;i<=n;i++)
        if(r[pp[i]]>r[i]||(r[pp[i]]==r[i]&&pp[i]<i)) cout<<pp[i]<<' ';
        else cout<<i<<' ';
    return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:102:23: warning: narrowing conversion of '(x[i] - r[i])' from 'long long int' to 'int' inside { } [-Wnarrowing]
         ev[++nr]={x[i]-r[i],i,1};
                   ~~~~^~~~~
circle_selection.cpp:103:28: warning: narrowing conversion of '((x[i] + r[i]) + 1)' from 'long long int' to 'int' inside { } [-Wnarrowing]
         ev[++nr]={x[i]+r[i]+1,i,-1};
                   ~~~~~~~~~^~
circle_selection.cpp:98:9: warning: variable 'X' set but not used [-Wunused-but-set-variable]
     int X,nr=0;
         ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 488 KB Output is correct
12 Correct 2 ms 536 KB Output is correct
13 Correct 2 ms 536 KB Output is correct
14 Correct 2 ms 536 KB Output is correct
15 Correct 2 ms 536 KB Output is correct
16 Correct 4 ms 536 KB Output is correct
17 Correct 3 ms 688 KB Output is correct
18 Correct 3 ms 688 KB Output is correct
19 Correct 10 ms 744 KB Output is correct
20 Correct 10 ms 744 KB Output is correct
21 Correct 11 ms 744 KB Output is correct
22 Correct 46 ms 860 KB Output is correct
23 Correct 45 ms 860 KB Output is correct
24 Correct 57 ms 860 KB Output is correct
25 Correct 48 ms 860 KB Output is correct
26 Correct 51 ms 940 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1251 ms 41564 KB Output is correct
2 Correct 1181 ms 41612 KB Output is correct
3 Correct 1280 ms 41612 KB Output is correct
4 Correct 1250 ms 41612 KB Output is correct
5 Correct 1318 ms 41612 KB Output is correct
6 Correct 1169 ms 41612 KB Output is correct
7 Correct 1091 ms 41612 KB Output is correct
8 Correct 1103 ms 41612 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 41612 KB Output is correct
2 Correct 209 ms 41612 KB Output is correct
3 Correct 657 ms 41612 KB Output is correct
4 Correct 746 ms 41612 KB Output is correct
5 Incorrect 740 ms 41612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 41612 KB Output is correct
2 Correct 583 ms 41612 KB Output is correct
3 Incorrect 744 ms 41612 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 488 KB Output is correct
12 Correct 2 ms 536 KB Output is correct
13 Correct 2 ms 536 KB Output is correct
14 Correct 2 ms 536 KB Output is correct
15 Correct 2 ms 536 KB Output is correct
16 Correct 4 ms 536 KB Output is correct
17 Correct 3 ms 688 KB Output is correct
18 Correct 3 ms 688 KB Output is correct
19 Correct 10 ms 744 KB Output is correct
20 Correct 10 ms 744 KB Output is correct
21 Correct 11 ms 744 KB Output is correct
22 Correct 46 ms 860 KB Output is correct
23 Correct 45 ms 860 KB Output is correct
24 Correct 57 ms 860 KB Output is correct
25 Correct 48 ms 860 KB Output is correct
26 Correct 51 ms 940 KB Output is correct
27 Incorrect 27 ms 41612 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 488 KB Output is correct
12 Correct 2 ms 536 KB Output is correct
13 Correct 2 ms 536 KB Output is correct
14 Correct 2 ms 536 KB Output is correct
15 Correct 2 ms 536 KB Output is correct
16 Correct 4 ms 536 KB Output is correct
17 Correct 3 ms 688 KB Output is correct
18 Correct 3 ms 688 KB Output is correct
19 Correct 10 ms 744 KB Output is correct
20 Correct 10 ms 744 KB Output is correct
21 Correct 11 ms 744 KB Output is correct
22 Correct 46 ms 860 KB Output is correct
23 Correct 45 ms 860 KB Output is correct
24 Correct 57 ms 860 KB Output is correct
25 Correct 48 ms 860 KB Output is correct
26 Correct 51 ms 940 KB Output is correct
27 Correct 1251 ms 41564 KB Output is correct
28 Correct 1181 ms 41612 KB Output is correct
29 Correct 1280 ms 41612 KB Output is correct
30 Correct 1250 ms 41612 KB Output is correct
31 Correct 1318 ms 41612 KB Output is correct
32 Correct 1169 ms 41612 KB Output is correct
33 Correct 1091 ms 41612 KB Output is correct
34 Correct 1103 ms 41612 KB Output is correct
35 Correct 2 ms 41612 KB Output is correct
36 Correct 209 ms 41612 KB Output is correct
37 Correct 657 ms 41612 KB Output is correct
38 Correct 746 ms 41612 KB Output is correct
39 Incorrect 740 ms 41612 KB Output isn't correct
40 Halted 0 ms 0 KB -