oj.uz

Submission #84485

# Submission time Handle Problem Language Result Execution time Memory
84485 2018-11-15T14:40:56 Z radoslav11 Circle selection (APIO18_circle_selection) C++14
15 / 100
 2615 ms 100072 KB 
/*
    https://codeforces.com/blog/entry/59650
*/

#include <bits/stdc++.h>
#define endl '\n'

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound

using namespace std;
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

struct Circle
{
    int idx, rad, x, y;
    Circle() { idx = rad = x = y = 0; }
    Circle(int _i, int _r, int _x, int _y)
    {
        idx = _i;
        rad = _r;
        x = _x;
        y = _y;
    }
};

inline int64_t sq(int x) { return x * 1ll * x; }
bool cmp(const Circle &a, const Circle &b) { return a.rad != b.rad ? a.rad > b.rad : a.idx < b.idx; }
bool intersect(const Circle &a, const Circle &b) { return sq(a.x - b.x) + sq(a.y - b.y) <= sq(a.rad + b.rad); }

int n;
int answer[MAXN];
Circle a[MAXN];

void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].rad;
        a[i].idx = i;
    }
}

map<pair<int, int>, vector<int> > M;

void rebuild(int block_size)
{
    M.clear();
    for(int i = 1; i <= n; i++)
        if(!answer[a[i].idx])
            M[{a[i].x / block_size, a[i].y / block_size}].push_back(i);
}

void solve()
{
    sort(a + 1, a + n + 1, cmp);

    int B = a[1].rad;
    rebuild(B);

    for(int i = 1; i <= n; i++)
    {
        if(answer[a[i].idx]) continue;

        while(a[i].rad * 2 < B)
        {
            B >>= 1;
            rebuild(B);
        }

        answer[a[i].idx] = a[i].idx;

        int x = a[i].x / B, y = a[i].y / B;
        for(int dx = -2; dx <= 2; dx++)
            for(int dy = -2; dy <= 2; dy++)
            {
                int nx = dx + x;
                int ny = dy + y;

                if(M.count({nx, ny}))
                    for(int j: M[{nx, ny}])
                        if(intersect(a[i], a[j]))
                            answer[a[j].idx] = a[i].idx;
            }
    }

    for(int i = 1; i <= n; i++)
        cout << answer[i] << " ";
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    read();
    solve();
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16760 KB Output is correct
2 Correct 16 ms 16940 KB Output is correct
3 Correct 16 ms 16940 KB Output is correct
4 Correct 16 ms 16940 KB Output is correct
5 Correct 16 ms 16940 KB Output is correct
6 Correct 16 ms 16940 KB Output is correct
7 Correct 15 ms 16940 KB Output is correct
8 Incorrect 16 ms 16940 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 20316 KB Output is correct
2 Incorrect 209 ms 21240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21240 KB Output is correct
2 Correct 603 ms 28916 KB Output is correct
3 Correct 2265 ms 53176 KB Output is correct
4 Correct 2327 ms 61292 KB Output is correct
5 Correct 2341 ms 63136 KB Output is correct
6 Correct 716 ms 63136 KB Output is correct
7 Correct 310 ms 63136 KB Output is correct
8 Correct 54 ms 63136 KB Output is correct
9 Correct 2615 ms 83680 KB Output is correct
10 Correct 2092 ms 85160 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1980 ms 92908 KB Output is correct
2 Correct 1408 ms 100072 KB Output is correct
3 Incorrect 606 ms 100072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16760 KB Output is correct
2 Correct 16 ms 16940 KB Output is correct
3 Correct 16 ms 16940 KB Output is correct
4 Correct 16 ms 16940 KB Output is correct
5 Correct 16 ms 16940 KB Output is correct
6 Correct 16 ms 16940 KB Output is correct
7 Correct 15 ms 16940 KB Output is correct
8 Incorrect 16 ms 16940 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16760 KB Output is correct
2 Correct 16 ms 16940 KB Output is correct
3 Correct 16 ms 16940 KB Output is correct
4 Correct 16 ms 16940 KB Output is correct
5 Correct 16 ms 16940 KB Output is correct
6 Correct 16 ms 16940 KB Output is correct
7 Correct 15 ms 16940 KB Output is correct
8 Incorrect 16 ms 16940 KB Output isn't correct
9 Halted 0 ms 0 KB -