Submission #499532

#	Time	Username	Problem	Language	Result	Execution time	Memory
499532		_martynas	Circle selection (APIO18_circle_selection)	C++14	100 / 100	2609 ms	729968 KiB

circle_selection

#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

using ll = long long;

const ll MOD = 1e9+7;

const int MAX_N = 3e5+5;

template<typename T>
inline T clamp(T x, T mn, T mx)
{
    return x > mx ? mx : (x < mn ? mn : x);
}

int n;
struct Node
{
    ll x, y, r;
    int p;
    bool visited;
} A[MAX_N];

struct LLNode
{
    int idx;
    LLNode* next = nullptr;

    inline LLNode()
    {
    }

    inline LLNode(const int & val)
        : idx(val)
    {
    }
} LLNodes[MAX_N];
int llcounter = 0;

inline LLNode* getLLNode()
{
    return &LLNodes[llcounter++];
}

int dup;
int inRange;

struct Quad;
inline Quad* getQuadNode();

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

    inline Quad()
    {
    }

    inline Quad(const ll & _l, const ll & _r, const ll & _bot, const ll & _top)
        : l(_l), r(_r), bot(_bot), top(_top)
    {
        sz = 0;
    }

    void add(const ll & x, const ll & y, const 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) {
            if(llnode == nullptr) {
                llnode = getLLNode();
                llnode->idx = idx;
            }
            else {
                dup++;
                LLNode* temp = getLLNode();
                temp->idx = idx;
                temp->next = llnode;
                llnode = temp;
            }
        }
        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] = getQuadNode();
                    childs[0]->l = l;
                    childs[0]->r = midH;
                    childs[0]->bot = bot;
                    childs[0]->top = midV;
                }
                else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > midV)) {
                    childs[1] = getQuadNode();
                    childs[1]->l = midH+1;
                    childs[1]->r = r;
                    childs[1]->bot = bot;
                    childs[1]->top = midV;
                }
                else if(childs[2] == nullptr && !(x < l || x > midH || y < midV+1 || y > top)) {
                    childs[2] = getQuadNode();
                    childs[2]->l = l;
                    childs[2]->r = midH;
                    childs[2]->bot = midV+1;
                    childs[2]->top = top;
                }
                else if(childs[3] == nullptr && !(x < midH+1 || x > r || y < midV+1 || y > top)) {
                    childs[3] = getQuadNode();
                    childs[3]->l = midH+1;
                    childs[3]->r = r;
                    childs[3]->bot = midV+1;
                    childs[3]->top = top;
                }
            }
            else if(l != r) {
                if(childs[0] == nullptr && !(x < l || x > midH || y < bot || y > top)) {
                    childs[0] = getQuadNode();
                    childs[0]->l = l;
                    childs[0]->r = midH;
                    childs[0]->bot = bot;
                    childs[0]->top = top;
                }
                else if(childs[1] == nullptr && !(x < midH+1 || x > r || y < bot || y > top)) {
                    childs[1] = getQuadNode();
                    childs[1]->l = midH+1;
                    childs[1]->r = r;
                    childs[1]->bot = bot;
                    childs[1]->top = top;
                }
            }
            else if(top != bot) {
                if(childs[0] == nullptr && !(x < l || x > r || y < bot || y > midV)) {
                    childs[0] = getQuadNode();
                    childs[0]->l = l;
                    childs[0]->r = r;
                    childs[0]->bot = bot;
                    childs[0]->top = midV;
                }
                else if(childs[1] == nullptr && !(x < l || x > r || y < midV+1 || y > top)) {
                    childs[1] = getQuadNode();
                    childs[1]->l = l;
                    childs[1]->r = r;
                    childs[1]->bot = midV+1;
                    childs[1]->top = top;
                }
            }

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

    void setInRange(const ll & x, const ll & y, const ll & radius, const int & idx)
    {
        if(x+radius < l || x-radius > r || y+radius < bot || y-radius > top || sz == 0) {
            return;
        }
        bool circleIntersectsRectangle =
            (l <= x && x <= r && bot <= y && y <= top) // circle center inside rectangle
            || ((y-clamp(y, bot, top))*(y-clamp(y, bot, top))+(x-l)*(x-l)<=radius*radius) // circle intersects or covers left side
            || ((y-clamp(y, bot, top))*(y-clamp(y, bot, top))+(x-r)*(x-r)<=radius*radius) // circle intersects or covers right side
            || ((y-bot)*(y-bot)+(x-clamp(x, l, r))*(x-clamp(x, l, r))<=radius*radius) // circle intersects or covers bot side
            || ((y-top)*(y-top)+(x-clamp(x, l, r))*(x-clamp(x, l, r))<=radius*radius) // circle intersects or covers top side
            ;
        if(!circleIntersectsRectangle) {
            return;
        }

//        cerr << "l = " << l << ", r = " << r << ", "
//             << "bot = " << bot << ", top = " << top << "\n";
        if(l == r && bot == top) {
            inRange++;
            while(llnode != nullptr &&
                (A[idx].r+A[llnode->idx].r)*(A[idx].r+A[llnode->idx].r)
                >= llabs(A[idx].x-A[llnode->idx].x)*llabs(A[idx].x-A[llnode->idx].x)
                +llabs(A[idx].y-A[llnode->idx].y)*llabs(A[idx].y-A[llnode->idx].y)) {
                A[llnode->idx].p = idx;
                A[llnode->idx].visited = true;
                sz--;
                llnode = llnode->next;
            }
            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;
    }
} QuadNodes[MAX_N*30];
int quadcounter = 0;
inline Quad* getQuadNode()
{
    return &QuadNodes[quadcounter++];
}

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

inline int nextInt()
{
	int c = getchar();
	while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
	}
	int x = 0;
	bool neg = false;
	if (c == '-') {
		neg = true;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x*10+(c-'0');
		c = getchar();
	}
	if (neg)
		return -x;
	return x;
}

int main()
{
    auto stop = steady_clock::now();

    n = nextInt();
    for(int i = 0; i < n; i++) {
        A[i].x = nextInt();
        A[i].y = nextInt();
        A[i].r = nextInt();
    }

    //cerr << "Exec: " << duration_cast<milliseconds>(steady_clock::now()-stop).count() << " ms\n";

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

    for(int i = n-1; i >= 0; i--) {
        int idx = I[i];
        //cerr << i << " started\n";
        Q.add(A[idx].x, A[idx].y, idx);
        //cerr << i << " finished\n";
    }

    for(int i = 0; i < n; i++) {
        int idx = I[i];
        if(A[idx].visited) continue;
        Q.setInRange(A[idx].x, A[idx].y, A[idx].r+(i+1<n?A[I[i+1]].r:0), idx);
    }

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

//    cerr << "Dupe: " << dup << "\n";
//    cerr << "In range: " << inRange << "\n";
//    cerr << "Exec: " << duration_cast<milliseconds>(steady_clock::now()-stop).count() << " ms\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
*/

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:242:10: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
  242 |     auto stop = steady_clock::now();
      |          ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 13 / 13