제출 #790956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790956		xetrk	원 고르기 (APIO18_circle_selection)	C++17	87 / 100	3081 ms	154164 KiB

circle_selection

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 30 / 30
• Subtask 6: 0 / 13