oj.uz

Submission #499264

# Submission time Handle Problem Language Result Execution time Memory
499264 2021-12-27T15:40:41 Z _martynas Circle selection (APIO18_circle_selection) C++11
38 / 100
 1815 ms 553348 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll MOD = 1e9+7;

const int MAX_N = 3e5+5;

int n;
ll X[MAX_N], Y[MAX_N], R[MAX_N];
int P[MAX_N];
bool visited[MAX_N];

struct Quad
{
    ll l, r, bot, top;
    array<Quad*, 4> childs = {};
    int idx;
    int sz;

    Quad()
    {
    }

    Quad(ll _l, ll _r, ll _bot, ll _top)
        : l(_l), r(_r), bot(_bot), top(_top)
    {
        idx = -1;
        sz = 0;
    }

    void add(int x, int y, int idx)
    {
        if(x < l || x > r || y < bot || y > top) {
            return;
        }

        sz++;
//        cerr << "l = " << l << ", r = " << r << ", "
//             << "bot = " << bot << ", top = " << top << "\n";
        if(l == r && bot == top) {
            this->idx = idx;
        }
        else {
            ll midH, midV;
            midH = l+(r-l)/2;
            midV = bot+(top-bot)/2;

            if(l != r && top != bot) {
                if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > midV)) {
                    childs[0] = new Quad(l, midH, bot, midV);
                }
                else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > midV)) {
                    childs[1] = new Quad(midH+1, r, bot, midV);
                }
                else if(childs[2] == nullptr && !(x < l || x > midH || y < midV+1 || y > top)) {
                    childs[2] = new Quad(l, midH, midV+1, top);
                }
                else if(childs[3] == nullptr && !(x < midH+1 || x > r || y < midV+1 || y > top)) {
                    childs[3] = new Quad(midH+1, r, midV+1, top);
                }
            }
            else if(l != r) {
                if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > top)) {
                    childs[0] = new Quad(l, midH, bot, midV);
                }
                else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > top)) {
                    childs[1] = new Quad(midH+1, r, bot, top);
                }
            }
            else if(top != bot) {
                if(childs[0] == nullptr && !(x < l || x > r || y < bot || y > midV)) {
                    childs[0] = new Quad(l, r, bot, midV);
                }
                else if(childs[1] == nullptr && !(x < l || x > r || y < midV+1 || y > top)) {
                    childs[1] = new Quad(l, r, midV+1, top);
                }
            }

            for(int k = 0; k < 4; k++) {
                if(childs[k] != nullptr) {
                    childs[k]->add(x, y, idx);
                }
            }
        }
    }

    void setInRange(int x, int y, int radius, int idx)
    {
        if(x+2*radius < l || x-2*radius > r || y+2*radius < bot || y-2*radius > top || sz == 0) {
            return;
        }

//        cerr << "l = " << l << ", r = " << r << ", "
//             << "bot = " << bot << ", top = " << top << "\n";
        if(l == r && bot == top) {
            if((R[idx]+R[this->idx])*(R[idx]+R[this->idx])
                >= llabs(X[idx]-X[this->idx])*llabs(X[idx]-X[this->idx])
                +llabs(Y[idx]-Y[this->idx])*llabs(Y[idx]-Y[this->idx])) {
                P[this->idx] = idx;
                visited[this->idx] = true;
                sz--;
            }
            return;
        }

        int cnt = 0;
        for(int k = 0; k < 4; k++) {
            if(childs[k] != nullptr) {
                childs[k]->setInRange(x, y, radius, idx);
                cnt += childs[k]->sz;
            }
        }
        sz = cnt;
    }
};

Quad Q(-1000000000, 1000000000, -1000000000, 1000000000);

int main()
{
//    cerr << "0:\n";
//    Q.add(0, 0, 0);
//    cerr << "1:\n";
//    Q.add(2, 2, 1);
//    cerr << "2:\n";
//    Q.add(-3, -3, 2);
//
//    cerr << "P:\n";
//    Q.setInRange(0, 1, 1, 3);
//    for(int i = 0; i < 3; i++) {
//        cerr << i << ": " << P[i] << "\n";
//    }

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> X[i] >> Y[i] >> R[i];
    }
    iota(P, P+n, 0);

    // *Don't* handle circles at the same position
//    map<pair<int, int>, int> M;
//    for(int i = 0; i < n; i++) {
//        auto it = M.find({X[i], Y[i]});
//        if(it != M.end()) {
//            if(R[it->second] < R[i]) {
//                visited[it->second] = true;
//                P[it->second] = i;
//                M[{X[i], Y[i]}] = i;
//            }
//            else {
//                visited[i] = true;
//                P[i] = it->second;
//            }
//        }
//        else {
//            M[{X[i], Y[i]}] = i;
//        }
//    }

    for(int i = 0; i < n; i++) {
        //cerr << i << " started\n";
        Q.add(X[i], Y[i], i);
        //cerr << i << " finished\n";
    }

    vector<int> I(n);
    iota(I.begin(), I.end(), 0);
    sort(I.begin(), I.end(),
    [&](int a, int b)
    {
        return R[a] > R[b] || (R[a] == R[b] && a < b);
    });

    for(int i = 0; i < n; i++) {
        int idx = I[i];
        if(visited[idx]) continue;
        Q.setInRange(X[idx], Y[idx], R[idx], idx);
    }

//    for(int i = 0; i < n; i++) {
//        cerr << i << ": " << P[i] << "\n";
//    }

    for(int i = 0; i < n; i++) {
        cout << 1+P[i] << " ";
    }
    cout << "\n";

    return 0;
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Incorrect 1 ms 428 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1149 ms 303848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 594 ms 190852 KB Output is correct
3 Correct 1795 ms 553144 KB Output is correct
4 Correct 1815 ms 553348 KB Output is correct
5 Correct 1684 ms 495668 KB Output is correct
6 Correct 789 ms 267600 KB Output is correct
7 Correct 421 ms 140440 KB Output is correct
8 Correct 69 ms 28896 KB Output is correct
9 Correct 1763 ms 502172 KB Output is correct
10 Correct 1567 ms 519472 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1659 ms 506748 KB Output is correct
2 Correct 1602 ms 483360 KB Output is correct
3 Correct 1504 ms 507740 KB Output is correct
4 Correct 1639 ms 522168 KB Output is correct
5 Correct 1552 ms 504372 KB Output is correct
6 Correct 1425 ms 498908 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Incorrect 1 ms 428 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Incorrect 1 ms 428 KB Output isn't correct
7 Halted 0 ms 0 KB -