Submission #773350

#	Time	Username	Problem	Language	Result	Execution time	Memory
773350		xetrk	Circle selection (APIO18_circle_selection)	C++14	87 / 100	3076 ms	38844 KiB

circle_selection

#pragma warning(disable:4996)

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


typedef long long ll;
typedef long double ld;

int n;

vector<vector<ll>> circle;

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

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

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

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;
        circle.push_back({ x,y,r });
        sortRadius.push_back({ r,i });
        sortX.push_back({ x,i });
        sortY.push_back({ y,i });
        skipX[i] = i + 1;
        skipY[i] = i + 1;
    }

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

    for (int i = 0; i < n; i++)
    {
        xIdx[sortX[i].second] = i;
        yIdx[sortY[i].second] = i;
    }


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

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

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


        x = circle[cur][0], y = circle[cur][1], r = circle[cur][2];
        if (curDelete < n - 1)
            r2 = r + sortRadius[curDelete + 1].first + 1;
        else
            r2 = r * 2 + 1;

        // a이하를 찾아야하는데 lower bound는  a이상인걸 찾으니까.. 근데 그 이하인걸 찾아야하니 1빼줌
        xMin = lower_bound(sortX.begin(), sortX.end(), pair<ll, int>(x - r2, -1), comp) - sortX.begin();
        xMax = upper_bound(sortX.begin(), sortX.end(), pair<ll, int>(x + r2, 301000), comp) - sortX.begin();

        yMin = lower_bound(sortY.begin(), sortY.end(), pair<ll, int>(y - r2, -1), comp) - sortY.begin();
        yMax = upper_bound(sortY.begin(), sortY.end(), pair<ll, int>(y + r2, 301000), comp) - sortY.begin();

        xMin--;
        yMin--;

        if (xMin < 0) xMin = 0;
        if (yMin < 0) yMin = 0;

        if (xMin >= sortX.size()) xMin = sortX.size() - 1;
        if (yMin >= sortY.size()) yMin = sortY.size() - 1;
        if (xMax >= sortX.size()) xMax = sortX.size() - 1;
        if (yMax >= sortY.size()) yMax = sortY.size() - 1;

        //xMin = 0, yMin = 0, xMax = n - 1, yMax = n - 1;


        ans[cur] = cur;
        if (xIdx[cur] - 1 >= 0)
        {
            skipX[xIdx[cur] - 1] = skipX[xIdx[cur]];
            if (skipX[xIdx[cur] - 1] == 0) skipX[xIdx[cur] - 1] = n + 1;
        }
        if (yIdx[cur] - 1 >= 0)
        {
            skipY[yIdx[cur] - 1] = skipY[yIdx[cur]];
            if (skipY[yIdx[cur] - 1] == 0) skipY[yIdx[cur] - 1] = n + 1;
        }
        //xIdx[cur]

        if (xMax - xMin < yMax - yMin)
        {
            i = xMin;
            while (i <= xMax)
            {
                curcmp = sortX[i].second;
                next = skipX[i];
                if (ans[curcmp] != -1)
                {
                    i = next;
                    continue;
                }
                rr = r + circle[curcmp][2];
                if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
                {
                    ans[curcmp] = cur;
                    //sortX.erase(sortX.begin() + i);
                    if (i - 1 >= 0)
                        skipX[i - 1] = skipX[i];

                    
                    if (yIdx[curcmp] - 1 >= 0)
                    {
                        skipY[yIdx[curcmp] - 1] = skipY[yIdx[curcmp]];
                        if (skipY[yIdx[curcmp] - 1] == 0) skipY[yIdx[curcmp] - 1] = n + 1;
                    }
                }
                i = next;
            }
        }
        else
        {
            i = yMin;
            while (i <= yMax)
            {
                curcmp = sortY[i].second;
                next = skipY[i];
                if (ans[curcmp] != -1)
                {
                    i = next;
                    continue;
                }
                rr = r + circle[curcmp][2];
                if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
                {
                    ans[curcmp] = cur;
                    //sortX.erase(sortX.begin() + i);
                    if (i - 1>= 0)
                        skipY[i - 1] = skipY[i];

                    
                    if (xIdx[curcmp] - 1 >= 0)
                    {
                        skipX[xIdx[curcmp] - 1] = skipX[xIdx[curcmp]];
                        if (skipX[xIdx[curcmp] - 1] == 0) skipX[xIdx[curcmp] - 1] = n + 1;
                    }
                }
                i = next;
            }
            /*
            for (int i = yMax; i >= yMin; i--)
            {
             curcmp = sortY[i].second;
             if (ans[curcmp]!= -1) continue;
             rr = r + circle[curcmp][2];
             if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
             {
              ans[curcmp] = cur;
              //sortY.erase(sortY.begin() + i);
             }
            }*/
        }
    }

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

    return 0;
}

Compilation message (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:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         if (xMin >= sortX.size()) xMin = sortX.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         if (yMin >= sortY.size()) yMin = sortY.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if (xMax >= sortX.size()) xMax = sortX.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         if (yMax >= sortY.size()) yMax = sortY.size() - 1;
      |             ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         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