oj.uz

답안 #260439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260439 2020-08-10T09:14:24 Z Kastanda 원 고르기 (APIO18_circle_selection) C++11
7 / 100
 3000 ms 394592 KB 
// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005;
int n, X[N], Y[N], R[N], M[N];
vector < int > UX;
vector < pair < int , int > > V[N * 2];
set < pair < int , int > > ST[N * 2];
inline int GetId(int a)
{
        return (int)(lower_bound(UX.begin(), UX.end(), a) - UX.begin());
}
inline bool Check(int i, int j)
{
        return ((ll)(X[i] - X[j]) * (ll)(X[i] - X[j]) + (ll)(Y[i] - Y[j]) * (ll)(Y[i] - Y[j]) <= (ll)(R[i] + R[j]) * (ll)(R[i] + R[j]));
}
inline void Get(int l, int r, int le, int ri, int i)
{
        l += (int)UX.size();
        r += (int)UX.size();
        for (; l < r; l >>= 1, r >>= 1)
        {
                if (l & 1)
                {
                        auto it = ST[l].lower_bound({le, -1});
                        while (it != ST[l].end() && it->first < ri)
                        {
                                if (M[it->second])
                                        it = ST[l].erase(it);
                                else if (Check(i, it->second))
                                        M[it->second] = i, it = ST[l].erase(it);
                                else
                                        it ++;
                        }
                        l ++;
                }
                if (r & 1)
                {
                        r --;
                        auto it = ST[r].lower_bound({le, -1});
                        while (it != ST[r].end() && it->first < ri)
                        {
                                if (M[it->second])
                                        it = ST[r].erase(it);
                                else if (Check(i, it->second))
                                        M[it->second] = i, it = ST[r].erase(it);
                                else
                                        it ++;
                        }
                }
        }
}
inline void Do(int i)
{
        M[i] = i;

        int lx = 0;
        int rx = (int)UX.size();
        int ly = -(int)(1e9 + 9);
        int ry = (int)(1e9 + 9);

        Get(lx, rx, ly, ry, i);
}
int main()
{
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++)
                scanf("%d%d%d", &X[i], &Y[i], &R[i]), UX.push_back(X[i]);
        sort(UX.begin(), UX.end());
        UX.resize(unique(UX.begin(), UX.end()) - UX.begin());
        for (int i = 1; i <= n; i ++)
        {
                int x = GetId(X[i]);
                V[x + (int)UX.size()].push_back({Y[i], i});
        }
        for (int i = (int)UX.size(); i < (int)UX.size() * 2; i ++)
                sort(V[i].begin(), V[i].end());
        for (int i = (int)UX.size() - 1; i; i --)
                merge(V[i << 1].begin(), V[i << 1].end(), V[i << 1 ^ 1].begin(), V[i << 1 ^ 1].end(), back_inserter(V[i]));
        for (int i = 0; i < (int)UX.size() * 2; i ++)
                ST[i] = set < pair < int , int > > (V[i].begin(), V[i].end());
        set < pair < int , int > > TS;
        for (int i = 1; i <= n; i ++)
                TS.insert({-R[i], i});
        while (TS.size())
        {
                while (TS.size() && M[TS.begin()->second])
                        TS.erase(TS.begin());
                if (!TS.size())
                        break;
                int i = TS.begin()->second;
                TS.erase(TS.begin());
                Do(i);
        }
        for (int i = 1; i <= n; i ++)
                printf("%d ", M[i]);
        printf("\n");
        return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &n);
         ~~~~~^~~~~~~~~~
circle_selection.cpp:69:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d%d", &X[i], &Y[i], &R[i]), UX.push_back(X[i]);
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 42600 KB Output is correct
2 Correct 27 ms 42624 KB Output is correct
3 Correct 27 ms 42624 KB Output is correct
4 Correct 33 ms 42624 KB Output is correct
5 Correct 27 ms 42616 KB Output is correct
6 Correct 29 ms 42692 KB Output is correct
7 Correct 27 ms 42616 KB Output is correct
8 Correct 27 ms 42624 KB Output is correct
9 Correct 27 ms 42624 KB Output is correct
10 Correct 28 ms 42624 KB Output is correct
11 Correct 28 ms 42624 KB Output is correct
12 Correct 27 ms 42744 KB Output is correct
13 Correct 27 ms 42648 KB Output is correct
14 Correct 27 ms 42624 KB Output is correct
15 Correct 27 ms 42624 KB Output is correct
16 Correct 30 ms 43384 KB Output is correct
17 Correct 30 ms 43384 KB Output is correct
18 Correct 29 ms 43392 KB Output is correct
19 Correct 42 ms 46968 KB Output is correct
20 Correct 41 ms 47096 KB Output is correct
21 Correct 41 ms 46968 KB Output is correct
22 Correct 178 ms 47096 KB Output is correct
23 Correct 181 ms 47096 KB Output is correct
24 Correct 207 ms 46968 KB Output is correct
25 Correct 180 ms 47096 KB Output is correct
26 Correct 183 ms 46968 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1455 ms 394564 KB Output is correct
2 Correct 1440 ms 394080 KB Output is correct
3 Correct 1378 ms 394592 KB Output is correct
4 Correct 1379 ms 393952 KB Output is correct
5 Execution timed out 3104 ms 390624 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 42624 KB Output is correct
2 Execution timed out 3036 ms 150436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3105 ms 391560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 42600 KB Output is correct
2 Correct 27 ms 42624 KB Output is correct
3 Correct 27 ms 42624 KB Output is correct
4 Correct 33 ms 42624 KB Output is correct
5 Correct 27 ms 42616 KB Output is correct
6 Correct 29 ms 42692 KB Output is correct
7 Correct 27 ms 42616 KB Output is correct
8 Correct 27 ms 42624 KB Output is correct
9 Correct 27 ms 42624 KB Output is correct
10 Correct 28 ms 42624 KB Output is correct
11 Correct 28 ms 42624 KB Output is correct
12 Correct 27 ms 42744 KB Output is correct
13 Correct 27 ms 42648 KB Output is correct
14 Correct 27 ms 42624 KB Output is correct
15 Correct 27 ms 42624 KB Output is correct
16 Correct 30 ms 43384 KB Output is correct
17 Correct 30 ms 43384 KB Output is correct
18 Correct 29 ms 43392 KB Output is correct
19 Correct 42 ms 46968 KB Output is correct
20 Correct 41 ms 47096 KB Output is correct
21 Correct 41 ms 46968 KB Output is correct
22 Correct 178 ms 47096 KB Output is correct
23 Correct 181 ms 47096 KB Output is correct
24 Correct 207 ms 46968 KB Output is correct
25 Correct 180 ms 47096 KB Output is correct
26 Correct 183 ms 46968 KB Output is correct
27 Correct 58 ms 51964 KB Output is correct
28 Correct 58 ms 51960 KB Output is correct
29 Correct 58 ms 51960 KB Output is correct
30 Correct 665 ms 52088 KB Output is correct
31 Correct 659 ms 51960 KB Output is correct
32 Correct 683 ms 52088 KB Output is correct
33 Correct 418 ms 154472 KB Output is correct
34 Correct 414 ms 154220 KB Output is correct
35 Correct 426 ms 154092 KB Output is correct
36 Execution timed out 3085 ms 152992 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 42600 KB Output is correct
2 Correct 27 ms 42624 KB Output is correct
3 Correct 27 ms 42624 KB Output is correct
4 Correct 33 ms 42624 KB Output is correct
5 Correct 27 ms 42616 KB Output is correct
6 Correct 29 ms 42692 KB Output is correct
7 Correct 27 ms 42616 KB Output is correct
8 Correct 27 ms 42624 KB Output is correct
9 Correct 27 ms 42624 KB Output is correct
10 Correct 28 ms 42624 KB Output is correct
11 Correct 28 ms 42624 KB Output is correct
12 Correct 27 ms 42744 KB Output is correct
13 Correct 27 ms 42648 KB Output is correct
14 Correct 27 ms 42624 KB Output is correct
15 Correct 27 ms 42624 KB Output is correct
16 Correct 30 ms 43384 KB Output is correct
17 Correct 30 ms 43384 KB Output is correct
18 Correct 29 ms 43392 KB Output is correct
19 Correct 42 ms 46968 KB Output is correct
20 Correct 41 ms 47096 KB Output is correct
21 Correct 41 ms 46968 KB Output is correct
22 Correct 178 ms 47096 KB Output is correct
23 Correct 181 ms 47096 KB Output is correct
24 Correct 207 ms 46968 KB Output is correct
25 Correct 180 ms 47096 KB Output is correct
26 Correct 183 ms 46968 KB Output is correct
27 Correct 1455 ms 394564 KB Output is correct
28 Correct 1440 ms 394080 KB Output is correct
29 Correct 1378 ms 394592 KB Output is correct
30 Correct 1379 ms 393952 KB Output is correct
31 Execution timed out 3104 ms 390624 KB Time limit exceeded
32 Halted 0 ms 0 KB -