oj.uz

답안 #791198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791198 2023-07-23T14:51:58 Z xetrk 원 고르기 (APIO18_circle_selection) C++14
0 / 100
 3000 ms 175660 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;
    ll gap = (gridSize - sortRadius[sortRadius.size() - 1].first * 2LL)/n + 1;
    ll curGapPos = n - 1;
    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 / 1.1 >= sortRadius[curDelete].first * 2LL && gridSize / 1.1 >= 1)
        {
            gridSize /= 1.1;
            gridAll = SetGrid(gridSize);
        }*/

        if (curGapPos * gap >= sortRadius[curDelete].first * 2LL)
        {
            curGapPos--;
            gridSize = sortRadius[curDelete].first * 2LL;
            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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 580 KB Output is correct
18 Correct 2 ms 704 KB Output is correct
19 Correct 7 ms 2516 KB Output is correct
20 Correct 7 ms 2240 KB Output is correct
21 Correct 11 ms 2260 KB Output is correct
22 Execution timed out 3071 ms 3284 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 886 ms 125176 KB Output is correct
2 Correct 1031 ms 125284 KB Output is correct
3 Correct 935 ms 124968 KB Output is correct
4 Correct 888 ms 125216 KB Output is correct
5 Execution timed out 3015 ms 123696 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 3034 ms 60800 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3100 ms 175660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 580 KB Output is correct
18 Correct 2 ms 704 KB Output is correct
19 Correct 7 ms 2516 KB Output is correct
20 Correct 7 ms 2240 KB Output is correct
21 Correct 11 ms 2260 KB Output is correct
22 Execution timed out 3071 ms 3284 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 580 KB Output is correct
18 Correct 2 ms 704 KB Output is correct
19 Correct 7 ms 2516 KB Output is correct
20 Correct 7 ms 2240 KB Output is correct
21 Correct 11 ms 2260 KB Output is correct
22 Execution timed out 3071 ms 3284 KB Time limit exceeded
23 Halted 0 ms 0 KB -