제출 #774059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774059		xetrk	원 고르기 (APIO18_circle_selection)	C++17	7 / 100	3086 ms	69000 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;
set<pair<ll, int>> 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.insert({ x,i });
        sortY.insert({ y,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);

    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;

        auto xMin = lower_bound(sortX.begin(), sortX.end(), pair<ll, int>(x - r2, -1), comp);
        auto xMax = upper_bound(sortX.begin(), sortX.end(), pair<ll, int>(x + r2, 301000), comp);

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

        //        xMin--;
        //        yMin--;

        if (xMin != sortX.begin()) xMin--;
        if (yMin != sortY.begin()) yMin--;

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


        ans[cur] = cur;
        //xIdx[cur]

        set<pair<ll, int>>::iterator curX = xMin, curY = yMin, nextX, nextY;
        bool isBreak = false;

        while (curX != sortX.end() && curY != sortY.end())
        {
            curcmp = (*curX).second;
            rr = r + circle[curcmp][2];

            ++curX;
            ++curY;
            nextX = curX;
            nextY = curY;
            curX--;
            curY--;

            if (curX == xMax || curY == yMax)
                isBreak = true;

            if (ans[curcmp] == -1 && GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
            {
                ans[curcmp] = cur;
                //sortX.erase(curX);
            }

            curcmp = (*curY).second;
            rr = r + circle[curcmp][2];

            if (ans[curcmp] == -1 && GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
            {
                ans[curcmp] = cur;
               //sortY.erase(curY);
            }

            if (isBreak)
                break;
            curX = nextX, curY = nextY;
        }


    }

    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:50:9: warning: unused variable 'i' [-Wunused-variable]
   50 |     int i;
      |         ^
circle_selection.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
circle_selection.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%lld %lld %lld", &x, &y, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13