oj.uz

답안 #774694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
774694 2023-07-06T01:52:17 Z xetrk 원 고르기 (APIO18_circle_selection) C++14
15 / 100
 2198 ms 174296 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;
}


map<pair<ll, ll>, multiset<vector<ll>>> SetGrid(ll gridSize)
{
    map<pair<ll, ll>, multiset<vector<ll>>> myGrid;
    ll x, y, r, i;
    for (auto c = circleSet.begin(); c != circleSet.end(); c++)
    {
        x = (*c)[0], y = (*c)[1], r = (*c)[2], i = (*c)[3];
        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 });
        }
    }

    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*4;
    map<pair<ll, ll>, multiset<vector<ll>>> gridAll = SetGrid(gridSize);
    ll gridX, gridY;
    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*4 && gridSize>2)
        {
            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;
        
        for (int curGridX = gridX - 1; curGridX <= gridX + 1; curGridX++)
        {
            for (int curGridY = gridY - 1; curGridY <= gridY + 1; 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 (GetDist(x, y, nx, ny) <= (r + nr) * (r + nr))
                    {
                        ans[ni] = cur ;
                        eraseItems.push_back(curCircle);

                        circleSet.erase({ nx,ny,nr,ni });
                    }
                }

                for (auto eraseIt : eraseItems)
                    curGrids.erase(eraseIt);

            }
        }
  
    }

    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:74:17: warning: unused variable 'r2' [-Wunused-variable]
   74 |     ll x, y, r, r2;
      |                 ^~
circle_selection.cpp:75:9: warning: unused variable 'i' [-Wunused-variable]
   75 |     int i;
      |         ^
circle_selection.cpp:96:14: warning: unused variable 'curcmp' [-Wunused-variable]
   96 |     int cur, curcmp;
      |              ^~~~~~
circle_selection.cpp:98:8: warning: unused variable 'rr' [-Wunused-variable]
   98 |     ll rr;
      |        ^~
circle_selection.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%lld %lld %lld", &x, &y, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 785 ms 136428 KB Output is correct
2 Incorrect 1072 ms 116884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 556 ms 49088 KB Output is correct
3 Correct 2083 ms 147580 KB Output is correct
4 Correct 2090 ms 147464 KB Output is correct
5 Correct 2020 ms 151912 KB Output is correct
6 Correct 727 ms 76800 KB Output is correct
7 Correct 304 ms 36404 KB Output is correct
8 Correct 39 ms 7008 KB Output is correct
9 Correct 2198 ms 174296 KB Output is correct
10 Correct 1817 ms 158364 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1626 ms 131048 KB Output is correct
2 Correct 1415 ms 130252 KB Output is correct
3 Incorrect 1928 ms 99096 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -