답안 #50325 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50325	2018-06-10T06:54:41 Z	yp155136	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	2611 ms	69448 KB

circle_selection

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

typedef long long LL;
typedef pair<LL,LL> Pt;
typedef pair<LL,LL> pii;

#define X first
#define Y second

#define F first
#define S second

inline Pt operator+(const Pt &p1,const Pt &p2)
{
    return make_pair(p1.X+p2.X,p1.Y+p2.Y);
}

inline Pt operator-(const Pt &p1,const Pt &p2)
{
    return make_pair(p1.X-p2.X,p1.Y-p2.Y);
}

inline LL operator*(const Pt &p1,const Pt &p2)
{
    return p1.X*p2.X + p1.Y*p2.Y;
}

inline LL operator^(const Pt &p1,const Pt &p2)
{
    return p1.X*p2.Y - p1.Y*p2.X;
}

int n;

const int N = 300006;

int a[N];

Pt p[N];
LL r[N];

bool vis[N];

set<pii> R_x,L_x,xx;  //store x[i]+r,x[i]-r

void del_index(int i,int a_val)
{
    a[i] = a_val;
    vis[i] = true;
    L_x.erase(L_x.find(make_pair(p[i].X-r[i],i)));
    R_x.erase(R_x.find(make_pair(p[i].X+r[i],i)));
    xx.erase(xx.find(make_pair(p[i].X,i)));
}

unordered_set<int> st[N];
map<pii,int> mp;

int dx[25] = {-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
int dy[25] = {-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2};

bool okay_r_same(int i,int j)
{
    if ( ( (p[i]-p[j])*(p[i]-p[j]) ) <= (r[i]+r[j])*(r[i]+r[j]) )
    {
        a[j] = i;
        vis[j] = true;
        return true;
    }
    return false;
}
//unordered_set<int> alive_index;

const int G = 1024;

unordered_map<LL,LL> mp2;

inline LL to_LL(pii p)
{
    return (p.F+1000000001+G)*(2000000001+G) + (p.S + 1000000001+G);
}

int lc[N],rc[N];  //linked list for alive things

void build_graph(int R)
{
    mp2.clear();
    int _=0;
    for (int i=rc[0];i!=n+1;i=rc[i])
    {
        pii id = make_pair(p[i].X/R,p[i].Y/R);
        if (mp2.find(to_LL(id)) == mp2.end())
        {
            _++;
            st[_].clear();
            mp2[to_LL(id)] = _;
        }
        st[ mp2[ to_LL(id) ] ].insert(i);
    }
}

//const int G = 7122;

inline void out(int x)
{
    if (x > 9)
    {
        out(x/10);
    }
    putchar(x%10 + '0');
}

double sqrt_num[102];

void build()
{
    for (int i=0;102>i;i++)
    {
        sqrt_num[i] = sqrt(i);
    }
}

void solve()
{
    priority_queue<pii> pq;
    rc[0] = 1;
    for (int i=1;n>=i;i++)
    {
        pq.push(make_pair(r[i],-i));
        //alive_index.insert(i);
        lc[i] = i-1;
        rc[i] = i+1;
    }
    LL R = -1;
    int now=0;
    while (!pq.empty())
    {
        pii pp=pq.top();
        pq.pop();
        int ii=-pp.S;
        ++now;
        if (vis[ii]) continue;
        //if (now%1000 == 0) cout << "now = " << now << endl;
        if (R == -1 || r[ii]*2 < R)
        {
            R = r[ii];
            build_graph(R);
        }
        pii id=make_pair(p[ii].X/R,p[ii].Y/R);
        for (int k=0;25>k;k++)
        {
            int ddx = abs(dx[k])-1 , ddy = abs(dy[k])-1;
            ddx = max(ddx,0);
            ddy = max(ddy,0);
            if (sqrt_num[ddx*ddx + ddy*ddy]*R+0.0001 > 2*r[ii]) continue;
            pii h = id+make_pair(dx[k],dy[k]);
            auto iter=mp2.find( to_LL(h) );
            if (iter == mp2.end()) continue;
            int __ = (*iter).S;
            vector<int> del_id;
            for (int j:st[__])
            {
                if (okay_r_same(ii,j))
                {
                    del_id.push_back(j);
                }
            }
            for (int j:del_id)
            {
                st[__].erase(j);
                lc[ rc[j] ] = lc[j];
                rc[ lc[j] ] = rc[j];
            }
        }
    }
    for (int i=1;n>=i;i++)
    {
        out(a[i]);
        if (i == n) putchar('\n');
        else putchar(' ');
    }
}

//#define getchar_unlocked getchar

inline int rit()
{
    int ret=0;
    int f=1;
    char c;
    do {
        c = getchar_unlocked();
        if (c == '-') f = -1;
    } while (c < '0' || c>'9');
    do {
        ret *= 10;
        ret += (c-'0');
        c = getchar_unlocked();
    } while ('0' <= c && c <= '9');
    return f*ret;
}

int main ()
{
    n = rit();
    for (int i=1;n>=i;i++)
    {
        p[i].X = rit() + G;
        p[i].Y = rit() + G;
        r[i] = rit();
    }
    solve();
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	16760 KB	Output is correct
2	Correct	19 ms	16996 KB	Output is correct
3	Correct	17 ms	17052 KB	Output is correct
4	Correct	17 ms	17052 KB	Output is correct
5	Correct	16 ms	17052 KB	Output is correct
6	Correct	16 ms	17052 KB	Output is correct
7	Correct	19 ms	17060 KB	Output is correct
8	Correct	16 ms	17060 KB	Output is correct
9	Correct	16 ms	17060 KB	Output is correct
10	Correct	16 ms	17060 KB	Output is correct
11	Correct	16 ms	17060 KB	Output is correct
12	Correct	16 ms	17060 KB	Output is correct
13	Correct	17 ms	17060 KB	Output is correct
14	Correct	17 ms	17060 KB	Output is correct
15	Correct	16 ms	17060 KB	Output is correct
16	Correct	16 ms	17148 KB	Output is correct
17	Correct	20 ms	17148 KB	Output is correct
18	Correct	17 ms	17148 KB	Output is correct
19	Correct	21 ms	17596 KB	Output is correct
20	Correct	20 ms	17728 KB	Output is correct
21	Correct	20 ms	17728 KB	Output is correct
22	Correct	29 ms	17888 KB	Output is correct
23	Correct	28 ms	17888 KB	Output is correct
24	Correct	29 ms	17888 KB	Output is correct
25	Correct	29 ms	17888 KB	Output is correct
26	Correct	28 ms	17888 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	223 ms	50692 KB	Output is correct
2	Correct	375 ms	50692 KB	Output is correct
3	Correct	315 ms	50692 KB	Output is correct
4	Correct	264 ms	50812 KB	Output is correct
5	Correct	682 ms	50812 KB	Output is correct
6	Correct	1306 ms	56392 KB	Output is correct
7	Correct	584 ms	56392 KB	Output is correct
8	Correct	723 ms	56392 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	56392 KB	Output is correct
2	Correct	536 ms	56392 KB	Output is correct
3	Correct	2307 ms	66380 KB	Output is correct
4	Correct	2186 ms	66380 KB	Output is correct
5	Correct	1845 ms	66380 KB	Output is correct
6	Correct	694 ms	66380 KB	Output is correct
7	Correct	259 ms	66380 KB	Output is correct
8	Correct	74 ms	66380 KB	Output is correct
9	Correct	2492 ms	66380 KB	Output is correct
10	Correct	1778 ms	66380 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2142 ms	66400 KB	Output is correct
2	Correct	2256 ms	66400 KB	Output is correct
3	Correct	907 ms	66400 KB	Output is correct
4	Correct	2242 ms	66428 KB	Output is correct
5	Correct	2097 ms	66428 KB	Output is correct
6	Correct	617 ms	66428 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	16760 KB	Output is correct
2	Correct	19 ms	16996 KB	Output is correct
3	Correct	17 ms	17052 KB	Output is correct
4	Correct	17 ms	17052 KB	Output is correct
5	Correct	16 ms	17052 KB	Output is correct
6	Correct	16 ms	17052 KB	Output is correct
7	Correct	19 ms	17060 KB	Output is correct
8	Correct	16 ms	17060 KB	Output is correct
9	Correct	16 ms	17060 KB	Output is correct
10	Correct	16 ms	17060 KB	Output is correct
11	Correct	16 ms	17060 KB	Output is correct
12	Correct	16 ms	17060 KB	Output is correct
13	Correct	17 ms	17060 KB	Output is correct
14	Correct	17 ms	17060 KB	Output is correct
15	Correct	16 ms	17060 KB	Output is correct
16	Correct	16 ms	17148 KB	Output is correct
17	Correct	20 ms	17148 KB	Output is correct
18	Correct	17 ms	17148 KB	Output is correct
19	Correct	21 ms	17596 KB	Output is correct
20	Correct	20 ms	17728 KB	Output is correct
21	Correct	20 ms	17728 KB	Output is correct
22	Correct	29 ms	17888 KB	Output is correct
23	Correct	28 ms	17888 KB	Output is correct
24	Correct	29 ms	17888 KB	Output is correct
25	Correct	29 ms	17888 KB	Output is correct
26	Correct	28 ms	17888 KB	Output is correct
27	Correct	23 ms	66428 KB	Output is correct
28	Correct	22 ms	66428 KB	Output is correct
29	Correct	23 ms	66428 KB	Output is correct
30	Correct	42 ms	66428 KB	Output is correct
31	Correct	42 ms	66428 KB	Output is correct
32	Correct	44 ms	66428 KB	Output is correct
33	Correct	93 ms	66428 KB	Output is correct
34	Correct	83 ms	66428 KB	Output is correct
35	Correct	117 ms	66428 KB	Output is correct
36	Correct	543 ms	66428 KB	Output is correct
37	Correct	629 ms	66428 KB	Output is correct
38	Correct	652 ms	66428 KB	Output is correct
39	Correct	620 ms	66428 KB	Output is correct
40	Correct	605 ms	66428 KB	Output is correct
41	Correct	611 ms	66428 KB	Output is correct
42	Correct	314 ms	66428 KB	Output is correct
43	Correct	472 ms	66428 KB	Output is correct
44	Correct	462 ms	66428 KB	Output is correct
45	Correct	445 ms	66428 KB	Output is correct
46	Correct	465 ms	66428 KB	Output is correct
47	Correct	433 ms	66428 KB	Output is correct
48	Correct	474 ms	66428 KB	Output is correct
49	Correct	379 ms	66428 KB	Output is correct
50	Correct	414 ms	66428 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	16760 KB	Output is correct
2	Correct	19 ms	16996 KB	Output is correct
3	Correct	17 ms	17052 KB	Output is correct
4	Correct	17 ms	17052 KB	Output is correct
5	Correct	16 ms	17052 KB	Output is correct
6	Correct	16 ms	17052 KB	Output is correct
7	Correct	19 ms	17060 KB	Output is correct
8	Correct	16 ms	17060 KB	Output is correct
9	Correct	16 ms	17060 KB	Output is correct
10	Correct	16 ms	17060 KB	Output is correct
11	Correct	16 ms	17060 KB	Output is correct
12	Correct	16 ms	17060 KB	Output is correct
13	Correct	17 ms	17060 KB	Output is correct
14	Correct	17 ms	17060 KB	Output is correct
15	Correct	16 ms	17060 KB	Output is correct
16	Correct	16 ms	17148 KB	Output is correct
17	Correct	20 ms	17148 KB	Output is correct
18	Correct	17 ms	17148 KB	Output is correct
19	Correct	21 ms	17596 KB	Output is correct
20	Correct	20 ms	17728 KB	Output is correct
21	Correct	20 ms	17728 KB	Output is correct
22	Correct	29 ms	17888 KB	Output is correct
23	Correct	28 ms	17888 KB	Output is correct
24	Correct	29 ms	17888 KB	Output is correct
25	Correct	29 ms	17888 KB	Output is correct
26	Correct	28 ms	17888 KB	Output is correct
27	Correct	223 ms	50692 KB	Output is correct
28	Correct	375 ms	50692 KB	Output is correct
29	Correct	315 ms	50692 KB	Output is correct
30	Correct	264 ms	50812 KB	Output is correct
31	Correct	682 ms	50812 KB	Output is correct
32	Correct	1306 ms	56392 KB	Output is correct
33	Correct	584 ms	56392 KB	Output is correct
34	Correct	723 ms	56392 KB	Output is correct
35	Correct	16 ms	56392 KB	Output is correct
36	Correct	536 ms	56392 KB	Output is correct
37	Correct	2307 ms	66380 KB	Output is correct
38	Correct	2186 ms	66380 KB	Output is correct
39	Correct	1845 ms	66380 KB	Output is correct
40	Correct	694 ms	66380 KB	Output is correct
41	Correct	259 ms	66380 KB	Output is correct
42	Correct	74 ms	66380 KB	Output is correct
43	Correct	2492 ms	66380 KB	Output is correct
44	Correct	1778 ms	66380 KB	Output is correct
45	Correct	2142 ms	66400 KB	Output is correct
46	Correct	2256 ms	66400 KB	Output is correct
47	Correct	907 ms	66400 KB	Output is correct
48	Correct	2242 ms	66428 KB	Output is correct
49	Correct	2097 ms	66428 KB	Output is correct
50	Correct	617 ms	66428 KB	Output is correct
51	Correct	23 ms	66428 KB	Output is correct
52	Correct	22 ms	66428 KB	Output is correct
53	Correct	23 ms	66428 KB	Output is correct
54	Correct	42 ms	66428 KB	Output is correct
55	Correct	42 ms	66428 KB	Output is correct
56	Correct	44 ms	66428 KB	Output is correct
57	Correct	93 ms	66428 KB	Output is correct
58	Correct	83 ms	66428 KB	Output is correct
59	Correct	117 ms	66428 KB	Output is correct
60	Correct	543 ms	66428 KB	Output is correct
61	Correct	629 ms	66428 KB	Output is correct
62	Correct	652 ms	66428 KB	Output is correct
63	Correct	620 ms	66428 KB	Output is correct
64	Correct	605 ms	66428 KB	Output is correct
65	Correct	611 ms	66428 KB	Output is correct
66	Correct	314 ms	66428 KB	Output is correct
67	Correct	472 ms	66428 KB	Output is correct
68	Correct	462 ms	66428 KB	Output is correct
69	Correct	445 ms	66428 KB	Output is correct
70	Correct	465 ms	66428 KB	Output is correct
71	Correct	433 ms	66428 KB	Output is correct
72	Correct	474 ms	66428 KB	Output is correct
73	Correct	379 ms	66428 KB	Output is correct
74	Correct	414 ms	66428 KB	Output is correct
75	Correct	358 ms	66428 KB	Output is correct
76	Correct	345 ms	66428 KB	Output is correct
77	Correct	258 ms	66428 KB	Output is correct
78	Correct	237 ms	66428 KB	Output is correct
79	Correct	490 ms	66428 KB	Output is correct
80	Correct	226 ms	66428 KB	Output is correct
81	Correct	2225 ms	66428 KB	Output is correct
82	Correct	2101 ms	66428 KB	Output is correct
83	Correct	2045 ms	66428 KB	Output is correct
84	Correct	2059 ms	66428 KB	Output is correct
85	Correct	2174 ms	66428 KB	Output is correct
86	Correct	2225 ms	66428 KB	Output is correct
87	Correct	2506 ms	66428 KB	Output is correct
88	Correct	2389 ms	69188 KB	Output is correct
89	Correct	2330 ms	69188 KB	Output is correct
90	Correct	2611 ms	69188 KB	Output is correct
91	Correct	2596 ms	69448 KB	Output is correct
92	Correct	2607 ms	69448 KB	Output is correct
93	Correct	2122 ms	69448 KB	Output is correct
94	Correct	2151 ms	69448 KB	Output is correct
95	Correct	2224 ms	69448 KB	Output is correct
96	Correct	2188 ms	69448 KB	Output is correct
97	Correct	2144 ms	69448 KB	Output is correct
98	Correct	1380 ms	69448 KB	Output is correct
99	Correct	2190 ms	69448 KB	Output is correct
100	Correct	1924 ms	69448 KB	Output is correct
101	Correct	1472 ms	69448 KB	Output is correct
102	Correct	1917 ms	69448 KB	Output is correct
103	Correct	1941 ms	69448 KB	Output is correct
104	Correct	2162 ms	69448 KB	Output is correct
105	Correct	1416 ms	69448 KB	Output is correct
106	Correct	1639 ms	69448 KB	Output is correct
107	Correct	1679 ms	69448 KB	Output is correct
108	Correct	1862 ms	69448 KB	Output is correct
109	Correct	1745 ms	69448 KB	Output is correct
110	Correct	1744 ms	69448 KB	Output is correct
111	Correct	1744 ms	69448 KB	Output is correct
112	Correct	1538 ms	69448 KB	Output is correct
113	Correct	1665 ms	69448 KB	Output is correct
114	Correct	1629 ms	69448 KB	Output is correct
115	Correct	1594 ms	69448 KB	Output is correct
116	Correct	1666 ms	69448 KB	Output is correct

답안 #50325

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