oj.uz

Submission #790956

# Submission time Handle Problem Language Result Execution time Memory
790956 2023-07-23T09:52:30 Z xetrk Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 154164 KB 
#pragma warning(disable:4996)

#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;


typedef long long ll;
typedef long double ld;

int n;

vector<vector<ll>> circle;

vector<pair<ll, int>> sortRadius;
//set<pair<ll,int>> sortX, sortY;

//int skipX[300100], skipY[300100];
//int xIdx[300100], yIdx[300100];

set<vector<ll>> circleSet;


int ans[301000];

inline ll GetDist(ll x1, ll y1, ll x2, ll y2)
{
    // 아 좌표값 마이너스도 들어오네
    ll xx = max(x1, x2) - min(x1, x2);
    ll yy = max(y1, y2) - min(y1, y2);
    return (xx * xx) + (yy * yy);
}



bool comp(const pair<ll, int>& a, const pair<ll, int>& b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
}

bool compSort(const pair<ll, int>& a, const pair<ll, int>& b)
{
    if (a.first == b.first)
        return a.second < b.second;

    return a.first > b.first;
}

inline ll Pos2ll(ll x, ll y)
{
    return y * 3000000001L + x;
}

unordered_map<ll, multiset<vector<ll>>> SetGrid(ll gridSize)
{
    unordered_map<ll, multiset<vector<ll>>> myGrid;
    ll x, y, r, i, posll;
    for (auto c = circleSet.begin(); c != circleSet.end(); c++)
    {
        x = (*c)[0], y = (*c)[1], r = (*c)[2], i = (*c)[3];
        posll = Pos2ll(x / gridSize, y / gridSize);
        auto iter = myGrid.insert({ posll ,{{x,y,r,i}} });
        if (iter.second == false)
        {
            //auto iter = myGrid.find(posll);
            iter.first->second.insert({ x,y,r,i });
        }
    }

    return myGrid;

}

int main()
{

    ll x, y, r, r2;
    int i;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%lld %lld %lld", &x, &y, &r);
        //x = 1, y = 1, r = 3;
        //좌표는 양수로만 그래야 그리드계산 편함
        //1000000000
        x += 1000000000L;
        y += 1000000000L;
        //1000000000
        circle.push_back({ x,y,r });
        circleSet.insert({ x,y,r,i });
        sortRadius.push_back({ r,i });
    }

    sort(sortRadius.begin(), sortRadius.end(), compSort);
    //sort(sortX.begin(), sortX.end());
    //sort(sortY.begin(), sortY.end());


    int cur, curcmp;
    //int xMin, xMax, yMin, yMax;
    ll rr;

    fill(ans, ans + n + 2, -1);

    ll gridSize = sortRadius[0].first * 2LL;
    unordered_map<ll, multiset<vector<ll>>> gridAll = SetGrid(gridSize);

    ll gridX, gridY;
    ll nx, ny, nr, gridll, curll;
    int ni;

    multiset<vector<ll>> curGrids;


    for (int curDelete = 0; curDelete < n; curDelete++)
    {
        cur = sortRadius[curDelete].second;
        if (ans[cur] != -1)
            continue;

        if (gridSize / 2 >= sortRadius[curDelete].first * 2LL && gridSize / 2 >= 1)
        {
            gridSize /= 2;
            gridAll = SetGrid(gridSize);
        }

        ans[cur] = cur;

        x = circle[cur][0], y = circle[cur][1], r = circle[cur][2];

        gridX = x / gridSize, gridY = y / gridSize;
        circleSet.erase({ x,y,r,cur });
        gridll = Pos2ll(gridX, gridY);

        (*gridAll.find(gridll)).second.erase({ x,y,r,cur });

        for (int curGridX = gridX - 1; curGridX <= gridX + 1; curGridX++)
        {
            for (int curGridY = gridY - 1; curGridY <= gridY + 1; curGridY++)
            {
                curll = Pos2ll(curGridX, curGridY);
                auto ggg = gridAll.find(curll);
                if (ggg == gridAll.end())
                    continue;
                curGrids = (*ggg).second;
                vector<multiset<vector<ll>>::iterator> eraseItems;
                auto nextCircle = curGrids.begin();
                multiset<vector<ll>>::iterator curCircle;
                while(nextCircle!=curGrids.end())
                {
                    curCircle = nextCircle;
                    nextCircle++;
                    nx = (*curCircle)[0], ny = (*curCircle)[1], nr = (*curCircle)[2], ni = (*curCircle)[3];
                    if (ans[ni] != -1)
                        continue;
                    if (GetDist(x, y, nx, ny) <= (r + nr) * (r + nr))
                    {
                        ans[ni] = cur;
                        //eraseItems.push_back(curCircle);
                        curGrids.erase(curCircle);

                        circleSet.erase({ nx,ny,nr,ni });//log n 최대 n번
                    }
                }

                //for (auto eraseIt : eraseItems)
                   // curGrids.erase(eraseIt);//log n 최대 n*32 번

            }
        }

    }

    for (int i = 0; i < n; i++)
        printf("%d ", ans[i] + 1);

    return 0;
}

Compilation message

circle_selection.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    1 | #pragma warning(disable:4996)
      | 
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:80:17: warning: unused variable 'r2' [-Wunused-variable]
   80 |     ll x, y, r, r2;
      |                 ^~
circle_selection.cpp:81:9: warning: unused variable 'i' [-Wunused-variable]
   81 |     int i;
      |         ^
circle_selection.cpp:103:14: warning: unused variable 'curcmp' [-Wunused-variable]
  103 |     int cur, curcmp;
      |              ^~~~~~
circle_selection.cpp:105:8: warning: unused variable 'rr' [-Wunused-variable]
  105 |     ll rr;
      |        ^~
circle_selection.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%lld %lld %lld", &x, &y, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 10 ms 2316 KB Output is correct
20 Correct 7 ms 2132 KB Output is correct
21 Correct 7 ms 2132 KB Output is correct
22 Correct 13 ms 2300 KB Output is correct
23 Correct 10 ms 2196 KB Output is correct
24 Correct 12 ms 2260 KB Output is correct
25 Correct 12 ms 2308 KB Output is correct
26 Correct 10 ms 2260 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 106188 KB Output is correct
2 Correct 786 ms 107072 KB Output is correct
3 Correct 801 ms 112200 KB Output is correct
4 Correct 732 ms 119116 KB Output is correct
5 Correct 785 ms 88760 KB Output is correct
6 Correct 1059 ms 99168 KB Output is correct
7 Correct 837 ms 89144 KB Output is correct
8 Correct 829 ms 90544 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 519 ms 40220 KB Output is correct
3 Correct 2004 ms 119168 KB Output is correct
4 Correct 2047 ms 119552 KB Output is correct
5 Correct 1924 ms 143436 KB Output is correct
6 Correct 737 ms 70472 KB Output is correct
7 Correct 278 ms 32392 KB Output is correct
8 Correct 32 ms 6488 KB Output is correct
9 Correct 2298 ms 154164 KB Output is correct
10 Correct 1837 ms 151468 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1465 ms 116528 KB Output is correct
2 Correct 1445 ms 116520 KB Output is correct
3 Correct 1123 ms 92024 KB Output is correct
4 Correct 1436 ms 116536 KB Output is correct
5 Correct 1452 ms 116528 KB Output is correct
6 Correct 1048 ms 90032 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 10 ms 2316 KB Output is correct
20 Correct 7 ms 2132 KB Output is correct
21 Correct 7 ms 2132 KB Output is correct
22 Correct 13 ms 2300 KB Output is correct
23 Correct 10 ms 2196 KB Output is correct
24 Correct 12 ms 2260 KB Output is correct
25 Correct 12 ms 2308 KB Output is correct
26 Correct 10 ms 2260 KB Output is correct
27 Correct 14 ms 3636 KB Output is correct
28 Correct 13 ms 3852 KB Output is correct
29 Correct 15 ms 3680 KB Output is correct
30 Correct 24 ms 4172 KB Output is correct
31 Correct 21 ms 4108 KB Output is correct
32 Correct 21 ms 4108 KB Output is correct
33 Correct 193 ms 41240 KB Output is correct
34 Correct 183 ms 35320 KB Output is correct
35 Correct 266 ms 33512 KB Output is correct
36 Correct 482 ms 40124 KB Output is correct
37 Correct 470 ms 40268 KB Output is correct
38 Correct 474 ms 40228 KB Output is correct
39 Correct 2681 ms 48300 KB Output is correct
40 Correct 2758 ms 52084 KB Output is correct
41 Correct 2652 ms 52220 KB Output is correct
42 Correct 264 ms 32396 KB Output is correct
43 Correct 342 ms 39008 KB Output is correct
44 Correct 327 ms 39072 KB Output is correct
45 Correct 361 ms 39012 KB Output is correct
46 Correct 312 ms 39000 KB Output is correct
47 Correct 355 ms 38996 KB Output is correct
48 Correct 352 ms 39004 KB Output is correct
49 Correct 336 ms 39016 KB Output is correct
50 Correct 337 ms 39012 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 10 ms 2316 KB Output is correct
20 Correct 7 ms 2132 KB Output is correct
21 Correct 7 ms 2132 KB Output is correct
22 Correct 13 ms 2300 KB Output is correct
23 Correct 10 ms 2196 KB Output is correct
24 Correct 12 ms 2260 KB Output is correct
25 Correct 12 ms 2308 KB Output is correct
26 Correct 10 ms 2260 KB Output is correct
27 Correct 679 ms 106188 KB Output is correct
28 Correct 786 ms 107072 KB Output is correct
29 Correct 801 ms 112200 KB Output is correct
30 Correct 732 ms 119116 KB Output is correct
31 Correct 785 ms 88760 KB Output is correct
32 Correct 1059 ms 99168 KB Output is correct
33 Correct 837 ms 89144 KB Output is correct
34 Correct 829 ms 90544 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 519 ms 40220 KB Output is correct
37 Correct 2004 ms 119168 KB Output is correct
38 Correct 2047 ms 119552 KB Output is correct
39 Correct 1924 ms 143436 KB Output is correct
40 Correct 737 ms 70472 KB Output is correct
41 Correct 278 ms 32392 KB Output is correct
42 Correct 32 ms 6488 KB Output is correct
43 Correct 2298 ms 154164 KB Output is correct
44 Correct 1837 ms 151468 KB Output is correct
45 Correct 1465 ms 116528 KB Output is correct
46 Correct 1445 ms 116520 KB Output is correct
47 Correct 1123 ms 92024 KB Output is correct
48 Correct 1436 ms 116536 KB Output is correct
49 Correct 1452 ms 116528 KB Output is correct
50 Correct 1048 ms 90032 KB Output is correct
51 Correct 14 ms 3636 KB Output is correct
52 Correct 13 ms 3852 KB Output is correct
53 Correct 15 ms 3680 KB Output is correct
54 Correct 24 ms 4172 KB Output is correct
55 Correct 21 ms 4108 KB Output is correct
56 Correct 21 ms 4108 KB Output is correct
57 Correct 193 ms 41240 KB Output is correct
58 Correct 183 ms 35320 KB Output is correct
59 Correct 266 ms 33512 KB Output is correct
60 Correct 482 ms 40124 KB Output is correct
61 Correct 470 ms 40268 KB Output is correct
62 Correct 474 ms 40228 KB Output is correct
63 Correct 2681 ms 48300 KB Output is correct
64 Correct 2758 ms 52084 KB Output is correct
65 Correct 2652 ms 52220 KB Output is correct
66 Correct 264 ms 32396 KB Output is correct
67 Correct 342 ms 39008 KB Output is correct
68 Correct 327 ms 39072 KB Output is correct
69 Correct 361 ms 39012 KB Output is correct
70 Correct 312 ms 39000 KB Output is correct
71 Correct 355 ms 38996 KB Output is correct
72 Correct 352 ms 39004 KB Output is correct
73 Correct 336 ms 39016 KB Output is correct
74 Correct 337 ms 39012 KB Output is correct
75 Correct 812 ms 115052 KB Output is correct
76 Correct 800 ms 107344 KB Output is correct
77 Correct 677 ms 123472 KB Output is correct
78 Correct 739 ms 108240 KB Output is correct
79 Correct 1223 ms 91256 KB Output is correct
80 Correct 723 ms 100580 KB Output is correct
81 Correct 1982 ms 117288 KB Output is correct
82 Correct 1987 ms 119276 KB Output is correct
83 Correct 2005 ms 119184 KB Output is correct
84 Correct 2040 ms 117136 KB Output is correct
85 Correct 2090 ms 117572 KB Output is correct
86 Correct 1965 ms 117264 KB Output is correct
87 Correct 2019 ms 117036 KB Output is correct
88 Execution timed out 3081 ms 154052 KB Time limit exceeded
89 Halted 0 ms 0 KB -