oj.uz

Submission #499279

# Submission time Handle Problem Language Result Execution time Memory
499279 2021-12-27T18:36:25 Z _martynas Circle selection (APIO18_circle_selection) C++14
87 / 100
 3000 ms 956996 KB 
#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;

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;

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+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) {
            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*40];
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, idx);
    }

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

    //cerr << "Dupe: " << dup << "\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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 944232 KB Output is correct
2 Correct 345 ms 944236 KB Output is correct
3 Correct 326 ms 944276 KB Output is correct
4 Correct 322 ms 944308 KB Output is correct
5 Correct 346 ms 944400 KB Output is correct
6 Correct 317 ms 944244 KB Output is correct
7 Correct 322 ms 944212 KB Output is correct
8 Correct 339 ms 944216 KB Output is correct
9 Correct 326 ms 944204 KB Output is correct
10 Correct 327 ms 944332 KB Output is correct
11 Correct 351 ms 944324 KB Output is correct
12 Correct 328 ms 944512 KB Output is correct
13 Correct 337 ms 944256 KB Output is correct
14 Correct 327 ms 944260 KB Output is correct
15 Correct 345 ms 944308 KB Output is correct
16 Correct 320 ms 944276 KB Output is correct
17 Correct 346 ms 944252 KB Output is correct
18 Correct 332 ms 944288 KB Output is correct
19 Correct 358 ms 944588 KB Output is correct
20 Correct 331 ms 944428 KB Output is correct
21 Correct 378 ms 944504 KB Output is correct
22 Correct 327 ms 944452 KB Output is correct
23 Correct 334 ms 944460 KB Output is correct
24 Correct 332 ms 944460 KB Output is correct
25 Correct 338 ms 944584 KB Output is correct
26 Correct 332 ms 944592 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1100 ms 956940 KB Output is correct
2 Correct 1131 ms 956996 KB Output is correct
3 Correct 1106 ms 956696 KB Output is correct
4 Correct 1148 ms 956944 KB Output is correct
5 Correct 839 ms 956704 KB Output is correct
6 Correct 1156 ms 956816 KB Output is correct
7 Correct 945 ms 956812 KB Output is correct
8 Correct 965 ms 956816 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 944356 KB Output is correct
2 Correct 703 ms 948372 KB Output is correct
3 Correct 1602 ms 956808 KB Output is correct
4 Correct 1593 ms 956816 KB Output is correct
5 Correct 1690 ms 956544 KB Output is correct
6 Correct 876 ms 950740 KB Output is correct
7 Correct 571 ms 947680 KB Output is correct
8 Correct 366 ms 945084 KB Output is correct
9 Correct 1578 ms 956820 KB Output is correct
10 Correct 1459 ms 956788 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1548 ms 956808 KB Output is correct
2 Correct 1516 ms 956808 KB Output is correct
3 Correct 1355 ms 956428 KB Output is correct
4 Correct 1480 ms 956812 KB Output is correct
5 Correct 1404 ms 956852 KB Output is correct
6 Correct 1153 ms 956180 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 944232 KB Output is correct
2 Correct 345 ms 944236 KB Output is correct
3 Correct 326 ms 944276 KB Output is correct
4 Correct 322 ms 944308 KB Output is correct
5 Correct 346 ms 944400 KB Output is correct
6 Correct 317 ms 944244 KB Output is correct
7 Correct 322 ms 944212 KB Output is correct
8 Correct 339 ms 944216 KB Output is correct
9 Correct 326 ms 944204 KB Output is correct
10 Correct 327 ms 944332 KB Output is correct
11 Correct 351 ms 944324 KB Output is correct
12 Correct 328 ms 944512 KB Output is correct
13 Correct 337 ms 944256 KB Output is correct
14 Correct 327 ms 944260 KB Output is correct
15 Correct 345 ms 944308 KB Output is correct
16 Correct 320 ms 944276 KB Output is correct
17 Correct 346 ms 944252 KB Output is correct
18 Correct 332 ms 944288 KB Output is correct
19 Correct 358 ms 944588 KB Output is correct
20 Correct 331 ms 944428 KB Output is correct
21 Correct 378 ms 944504 KB Output is correct
22 Correct 327 ms 944452 KB Output is correct
23 Correct 334 ms 944460 KB Output is correct
24 Correct 332 ms 944460 KB Output is correct
25 Correct 338 ms 944584 KB Output is correct
26 Correct 332 ms 944592 KB Output is correct
27 Correct 357 ms 944676 KB Output is correct
28 Correct 363 ms 944672 KB Output is correct
29 Correct 340 ms 944632 KB Output is correct
30 Correct 353 ms 944628 KB Output is correct
31 Correct 386 ms 944660 KB Output is correct
32 Correct 350 ms 944804 KB Output is correct
33 Correct 568 ms 948412 KB Output is correct
34 Correct 580 ms 948488 KB Output is correct
35 Correct 619 ms 948372 KB Output is correct
36 Correct 676 ms 948400 KB Output is correct
37 Correct 648 ms 948376 KB Output is correct
38 Correct 650 ms 948368 KB Output is correct
39 Correct 1437 ms 948448 KB Output is correct
40 Correct 1432 ms 948376 KB Output is correct
41 Correct 1427 ms 948376 KB Output is correct
42 Correct 590 ms 948384 KB Output is correct
43 Correct 631 ms 948368 KB Output is correct
44 Correct 648 ms 948480 KB Output is correct
45 Correct 665 ms 948372 KB Output is correct
46 Correct 657 ms 948380 KB Output is correct
47 Correct 623 ms 948352 KB Output is correct
48 Correct 673 ms 948372 KB Output is correct
49 Correct 673 ms 948320 KB Output is correct
50 Correct 631 ms 948380 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 944232 KB Output is correct
2 Correct 345 ms 944236 KB Output is correct
3 Correct 326 ms 944276 KB Output is correct
4 Correct 322 ms 944308 KB Output is correct
5 Correct 346 ms 944400 KB Output is correct
6 Correct 317 ms 944244 KB Output is correct
7 Correct 322 ms 944212 KB Output is correct
8 Correct 339 ms 944216 KB Output is correct
9 Correct 326 ms 944204 KB Output is correct
10 Correct 327 ms 944332 KB Output is correct
11 Correct 351 ms 944324 KB Output is correct
12 Correct 328 ms 944512 KB Output is correct
13 Correct 337 ms 944256 KB Output is correct
14 Correct 327 ms 944260 KB Output is correct
15 Correct 345 ms 944308 KB Output is correct
16 Correct 320 ms 944276 KB Output is correct
17 Correct 346 ms 944252 KB Output is correct
18 Correct 332 ms 944288 KB Output is correct
19 Correct 358 ms 944588 KB Output is correct
20 Correct 331 ms 944428 KB Output is correct
21 Correct 378 ms 944504 KB Output is correct
22 Correct 327 ms 944452 KB Output is correct
23 Correct 334 ms 944460 KB Output is correct
24 Correct 332 ms 944460 KB Output is correct
25 Correct 338 ms 944584 KB Output is correct
26 Correct 332 ms 944592 KB Output is correct
27 Correct 1100 ms 956940 KB Output is correct
28 Correct 1131 ms 956996 KB Output is correct
29 Correct 1106 ms 956696 KB Output is correct
30 Correct 1148 ms 956944 KB Output is correct
31 Correct 839 ms 956704 KB Output is correct
32 Correct 1156 ms 956816 KB Output is correct
33 Correct 945 ms 956812 KB Output is correct
34 Correct 965 ms 956816 KB Output is correct
35 Correct 378 ms 944356 KB Output is correct
36 Correct 703 ms 948372 KB Output is correct
37 Correct 1602 ms 956808 KB Output is correct
38 Correct 1593 ms 956816 KB Output is correct
39 Correct 1690 ms 956544 KB Output is correct
40 Correct 876 ms 950740 KB Output is correct
41 Correct 571 ms 947680 KB Output is correct
42 Correct 366 ms 945084 KB Output is correct
43 Correct 1578 ms 956820 KB Output is correct
44 Correct 1459 ms 956788 KB Output is correct
45 Correct 1548 ms 956808 KB Output is correct
46 Correct 1516 ms 956808 KB Output is correct
47 Correct 1355 ms 956428 KB Output is correct
48 Correct 1480 ms 956812 KB Output is correct
49 Correct 1404 ms 956852 KB Output is correct
50 Correct 1153 ms 956180 KB Output is correct
51 Correct 357 ms 944676 KB Output is correct
52 Correct 363 ms 944672 KB Output is correct
53 Correct 340 ms 944632 KB Output is correct
54 Correct 353 ms 944628 KB Output is correct
55 Correct 386 ms 944660 KB Output is correct
56 Correct 350 ms 944804 KB Output is correct
57 Correct 568 ms 948412 KB Output is correct
58 Correct 580 ms 948488 KB Output is correct
59 Correct 619 ms 948372 KB Output is correct
60 Correct 676 ms 948400 KB Output is correct
61 Correct 648 ms 948376 KB Output is correct
62 Correct 650 ms 948368 KB Output is correct
63 Correct 1437 ms 948448 KB Output is correct
64 Correct 1432 ms 948376 KB Output is correct
65 Correct 1427 ms 948376 KB Output is correct
66 Correct 590 ms 948384 KB Output is correct
67 Correct 631 ms 948368 KB Output is correct
68 Correct 648 ms 948480 KB Output is correct
69 Correct 665 ms 948372 KB Output is correct
70 Correct 657 ms 948380 KB Output is correct
71 Correct 623 ms 948352 KB Output is correct
72 Correct 673 ms 948372 KB Output is correct
73 Correct 673 ms 948320 KB Output is correct
74 Correct 631 ms 948380 KB Output is correct
75 Correct 1223 ms 956684 KB Output is correct
76 Correct 1113 ms 956940 KB Output is correct
77 Correct 1150 ms 956996 KB Output is correct
78 Correct 1139 ms 956588 KB Output is correct
79 Correct 1377 ms 956836 KB Output is correct
80 Correct 1142 ms 956652 KB Output is correct
81 Correct 1477 ms 956844 KB Output is correct
82 Correct 1449 ms 956828 KB Output is correct
83 Correct 1501 ms 956868 KB Output is correct
84 Correct 1438 ms 956940 KB Output is correct
85 Correct 1442 ms 956816 KB Output is correct
86 Correct 1454 ms 956816 KB Output is correct
87 Correct 1444 ms 956892 KB Output is correct
88 Execution timed out 3140 ms 954920 KB Time limit exceeded
89 Halted 0 ms 0 KB -