oj.uz

Submission #790929

# Submission time Handle Problem Language Result Execution time Memory
790929 2023-07-23T09:30:09 Z xetrk Circle selection (APIO18_circle_selection) C++17
87 / 100
 3000 ms 166376 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 -1;
    return y * 3000000001L + x;
}

map<pair<ll, ll>, multiset<vector<ll>>> SetGrid(ll gridSize)
{
    map<pair<ll, 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);
        /*
        if (myGrid.insert({ {x / gridSize, y / gridSize},{{x,y,r,i}} }).second == false)
        {
            auto iter = myGrid.find({ x / gridSize, y / gridSize });
            (*iter).second.insert({ x,y,r,i });
        }*/
        auto iter = myGrid.insert({ {x / gridSize, y / gridSize},{{x,y,r,i}} });
        if (iter.second == false)
        {
            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;
        //좌표는 양수로만 그래야 그리드계산 편함
        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;
    map<pair<ll, ll>, multiset<vector<ll>>> gridAll = SetGrid(gridSize);
    ll gridX, gridY, gridll, curll;
    ll nx, ny, nr;
    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({ gridX,gridY })).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({ curGridX, curGridY });
                if (ggg == gridAll.end())
                    continue;
                curGrids = (*ggg).second;
                vector<multiset<vector<ll>>::iterator> eraseItems;
                for (auto curCircle = curGrids.begin(); curCircle != curGrids.end(); curCircle++)
                {
                    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);

                        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 'std::map<std::pair<long long int, long long int>, std::multiset<std::vector<long long int> > > SetGrid(ll)':
circle_selection.cpp:61:20: warning: variable 'posll' set but not used [-Wunused-but-set-variable]
   61 |     ll x, y, r, i, posll;
      |                    ^~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:87:17: warning: unused variable 'r2' [-Wunused-variable]
   87 |     ll x, y, r, r2;
      |                 ^~
circle_selection.cpp:88:9: warning: unused variable 'i' [-Wunused-variable]
   88 |     int i;
      |         ^
circle_selection.cpp:109:14: warning: unused variable 'curcmp' [-Wunused-variable]
  109 |     int cur, curcmp;
      |              ^~~~~~
circle_selection.cpp:111:8: warning: unused variable 'rr' [-Wunused-variable]
  111 |     ll rr;
      |        ^~
circle_selection.cpp:117:22: warning: variable 'gridll' set but not used [-Wunused-but-set-variable]
  117 |     ll gridX, gridY, gridll, curll;
      |                      ^~~~~~
circle_selection.cpp:117:30: warning: variable 'curll' set but not used [-Wunused-but-set-variable]
  117 |     ll gridX, gridY, gridll, curll;
      |                              ^~~~~
circle_selection.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf("%lld %lld %lld", &x, &y, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 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 672 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 7 ms 2496 KB Output is correct
20 Correct 7 ms 2260 KB Output is correct
21 Correct 8 ms 2388 KB Output is correct
22 Correct 13 ms 2472 KB Output is correct
23 Correct 13 ms 2512 KB Output is correct
24 Correct 14 ms 2516 KB Output is correct
25 Correct 12 ms 2496 KB Output is correct
26 Correct 12 ms 2528 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 109720 KB Output is correct
2 Correct 945 ms 110604 KB Output is correct
3 Correct 865 ms 114444 KB Output is correct
4 Correct 793 ms 123772 KB Output is correct
5 Correct 823 ms 91224 KB Output is correct
6 Correct 1183 ms 100292 KB Output is correct
7 Correct 834 ms 91744 KB Output is correct
8 Correct 943 ms 92988 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 628 ms 41496 KB Output is correct
3 Correct 2283 ms 123732 KB Output is correct
4 Correct 2618 ms 123600 KB Output is correct
5 Correct 2258 ms 152400 KB Output is correct
6 Correct 797 ms 73940 KB Output is correct
7 Correct 337 ms 34144 KB Output is correct
8 Correct 35 ms 7032 KB Output is correct
9 Correct 2219 ms 166376 KB Output is correct
10 Correct 1786 ms 158584 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1661 ms 123960 KB Output is correct
2 Correct 1495 ms 123936 KB Output is correct
3 Correct 1160 ms 92932 KB Output is correct
4 Correct 1433 ms 123688 KB Output is correct
5 Correct 1480 ms 123680 KB Output is correct
6 Correct 1152 ms 90644 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 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 672 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 7 ms 2496 KB Output is correct
20 Correct 7 ms 2260 KB Output is correct
21 Correct 8 ms 2388 KB Output is correct
22 Correct 13 ms 2472 KB Output is correct
23 Correct 13 ms 2512 KB Output is correct
24 Correct 14 ms 2516 KB Output is correct
25 Correct 12 ms 2496 KB Output is correct
26 Correct 12 ms 2528 KB Output is correct
27 Correct 14 ms 3980 KB Output is correct
28 Correct 14 ms 4108 KB Output is correct
29 Correct 18 ms 3880 KB Output is correct
30 Correct 33 ms 4612 KB Output is correct
31 Correct 26 ms 4612 KB Output is correct
32 Correct 25 ms 4612 KB Output is correct
33 Correct 195 ms 43540 KB Output is correct
34 Correct 199 ms 36772 KB Output is correct
35 Correct 273 ms 34748 KB Output is correct
36 Correct 560 ms 41736 KB Output is correct
37 Correct 516 ms 41796 KB Output is correct
38 Correct 539 ms 41732 KB Output is correct
39 Correct 2703 ms 49788 KB Output is correct
40 Correct 2726 ms 52564 KB Output is correct
41 Correct 2728 ms 52464 KB Output is correct
42 Correct 316 ms 33068 KB Output is correct
43 Correct 345 ms 40788 KB Output is correct
44 Correct 362 ms 40760 KB Output is correct
45 Correct 339 ms 40740 KB Output is correct
46 Correct 351 ms 40772 KB Output is correct
47 Correct 340 ms 40760 KB Output is correct
48 Correct 360 ms 40804 KB Output is correct
49 Correct 341 ms 40816 KB Output is correct
50 Correct 349 ms 40764 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 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 672 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 7 ms 2496 KB Output is correct
20 Correct 7 ms 2260 KB Output is correct
21 Correct 8 ms 2388 KB Output is correct
22 Correct 13 ms 2472 KB Output is correct
23 Correct 13 ms 2512 KB Output is correct
24 Correct 14 ms 2516 KB Output is correct
25 Correct 12 ms 2496 KB Output is correct
26 Correct 12 ms 2528 KB Output is correct
27 Correct 893 ms 109720 KB Output is correct
28 Correct 945 ms 110604 KB Output is correct
29 Correct 865 ms 114444 KB Output is correct
30 Correct 793 ms 123772 KB Output is correct
31 Correct 823 ms 91224 KB Output is correct
32 Correct 1183 ms 100292 KB Output is correct
33 Correct 834 ms 91744 KB Output is correct
34 Correct 943 ms 92988 KB Output is correct
35 Correct 0 ms 308 KB Output is correct
36 Correct 628 ms 41496 KB Output is correct
37 Correct 2283 ms 123732 KB Output is correct
38 Correct 2618 ms 123600 KB Output is correct
39 Correct 2258 ms 152400 KB Output is correct
40 Correct 797 ms 73940 KB Output is correct
41 Correct 337 ms 34144 KB Output is correct
42 Correct 35 ms 7032 KB Output is correct
43 Correct 2219 ms 166376 KB Output is correct
44 Correct 1786 ms 158584 KB Output is correct
45 Correct 1661 ms 123960 KB Output is correct
46 Correct 1495 ms 123936 KB Output is correct
47 Correct 1160 ms 92932 KB Output is correct
48 Correct 1433 ms 123688 KB Output is correct
49 Correct 1480 ms 123680 KB Output is correct
50 Correct 1152 ms 90644 KB Output is correct
51 Correct 14 ms 3980 KB Output is correct
52 Correct 14 ms 4108 KB Output is correct
53 Correct 18 ms 3880 KB Output is correct
54 Correct 33 ms 4612 KB Output is correct
55 Correct 26 ms 4612 KB Output is correct
56 Correct 25 ms 4612 KB Output is correct
57 Correct 195 ms 43540 KB Output is correct
58 Correct 199 ms 36772 KB Output is correct
59 Correct 273 ms 34748 KB Output is correct
60 Correct 560 ms 41736 KB Output is correct
61 Correct 516 ms 41796 KB Output is correct
62 Correct 539 ms 41732 KB Output is correct
63 Correct 2703 ms 49788 KB Output is correct
64 Correct 2726 ms 52564 KB Output is correct
65 Correct 2728 ms 52464 KB Output is correct
66 Correct 316 ms 33068 KB Output is correct
67 Correct 345 ms 40788 KB Output is correct
68 Correct 362 ms 40760 KB Output is correct
69 Correct 339 ms 40740 KB Output is correct
70 Correct 351 ms 40772 KB Output is correct
71 Correct 340 ms 40760 KB Output is correct
72 Correct 360 ms 40804 KB Output is correct
73 Correct 341 ms 40816 KB Output is correct
74 Correct 349 ms 40764 KB Output is correct
75 Correct 970 ms 118840 KB Output is correct
76 Correct 926 ms 109356 KB Output is correct
77 Correct 765 ms 129964 KB Output is correct
78 Correct 821 ms 111672 KB Output is correct
79 Correct 1252 ms 91484 KB Output is correct
80 Correct 840 ms 102480 KB Output is correct
81 Correct 2172 ms 123320 KB Output is correct
82 Correct 2107 ms 123200 KB Output is correct
83 Correct 2116 ms 123200 KB Output is correct
84 Correct 2231 ms 123100 KB Output is correct
85 Correct 2104 ms 123192 KB Output is correct
86 Correct 2087 ms 123232 KB Output is correct
87 Correct 2372 ms 122404 KB Output is correct
88 Execution timed out 3081 ms 154160 KB Time limit exceeded
89 Halted 0 ms 0 KB -