답안 #54093 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54093	2018-07-02T10:11:01 Z	Bodo171	원 고르기 (APIO18_circle_selection)	C++14	19 / 100	1455 ms	84604 KB

circle_selection

#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 tt[nmax];
int n,i,j,ind;
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;
}
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;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	464 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	2 ms	712 KB	Output is correct
12	Correct	2 ms	712 KB	Output is correct
13	Correct	3 ms	712 KB	Output is correct
14	Correct	2 ms	712 KB	Output is correct
15	Correct	2 ms	712 KB	Output is correct
16	Correct	3 ms	712 KB	Output is correct
17	Correct	4 ms	764 KB	Output is correct
18	Correct	5 ms	764 KB	Output is correct
19	Correct	18 ms	764 KB	Output is correct
20	Correct	10 ms	800 KB	Output is correct
21	Correct	11 ms	808 KB	Output is correct
22	Correct	44 ms	840 KB	Output is correct
23	Correct	46 ms	876 KB	Output is correct
24	Correct	45 ms	876 KB	Output is correct
25	Correct	43 ms	876 KB	Output is correct
26	Correct	46 ms	876 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1129 ms	45808 KB	Output is correct
2	Correct	1455 ms	52512 KB	Output is correct
3	Correct	1217 ms	58944 KB	Output is correct
4	Correct	1120 ms	65968 KB	Output is correct
5	Correct	1016 ms	70268 KB	Output is correct
6	Correct	1054 ms	75072 KB	Output is correct
7	Correct	1051 ms	80004 KB	Output is correct
8	Correct	990 ms	84604 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	84604 KB	Output is correct
2	Incorrect	140 ms	84604 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	434 ms	84604 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	464 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	2 ms	712 KB	Output is correct
12	Correct	2 ms	712 KB	Output is correct
13	Correct	3 ms	712 KB	Output is correct
14	Correct	2 ms	712 KB	Output is correct
15	Correct	2 ms	712 KB	Output is correct
16	Correct	3 ms	712 KB	Output is correct
17	Correct	4 ms	764 KB	Output is correct
18	Correct	5 ms	764 KB	Output is correct
19	Correct	18 ms	764 KB	Output is correct
20	Correct	10 ms	800 KB	Output is correct
21	Correct	11 ms	808 KB	Output is correct
22	Correct	44 ms	840 KB	Output is correct
23	Correct	46 ms	876 KB	Output is correct
24	Correct	45 ms	876 KB	Output is correct
25	Correct	43 ms	876 KB	Output is correct
26	Correct	46 ms	876 KB	Output is correct
27	Incorrect	20 ms	84604 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	464 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	640 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	2 ms	712 KB	Output is correct
12	Correct	2 ms	712 KB	Output is correct
13	Correct	3 ms	712 KB	Output is correct
14	Correct	2 ms	712 KB	Output is correct
15	Correct	2 ms	712 KB	Output is correct
16	Correct	3 ms	712 KB	Output is correct
17	Correct	4 ms	764 KB	Output is correct
18	Correct	5 ms	764 KB	Output is correct
19	Correct	18 ms	764 KB	Output is correct
20	Correct	10 ms	800 KB	Output is correct
21	Correct	11 ms	808 KB	Output is correct
22	Correct	44 ms	840 KB	Output is correct
23	Correct	46 ms	876 KB	Output is correct
24	Correct	45 ms	876 KB	Output is correct
25	Correct	43 ms	876 KB	Output is correct
26	Correct	46 ms	876 KB	Output is correct
27	Correct	1129 ms	45808 KB	Output is correct
28	Correct	1455 ms	52512 KB	Output is correct
29	Correct	1217 ms	58944 KB	Output is correct
30	Correct	1120 ms	65968 KB	Output is correct
31	Correct	1016 ms	70268 KB	Output is correct
32	Correct	1054 ms	75072 KB	Output is correct
33	Correct	1051 ms	80004 KB	Output is correct
34	Correct	990 ms	84604 KB	Output is correct
35	Correct	2 ms	84604 KB	Output is correct
36	Incorrect	140 ms	84604 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

답안 #54093

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0