oj.uz

Submission #52713

# Submission time Handle Problem Language Result Execution time Memory
52713 2018-06-26T12:10:16 Z Kubalionzzale Circle selection (APIO18_circle_selection) C++14
12 / 100
 2293 ms 49684 KB 
#include <iostream>
#include <set>
#include <math.h>
#include <algorithm>
#include <functional>
#include <iterator>

long double abss(long double x)
{
    if (x < 0)
        return -x;
    else
        return x;
}

long double sqr(long double x)
{
    return x * x;
}

struct compare {
    bool operator() (const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) const {
        if (lhs.first != rhs.first)
            return lhs.first > rhs.first;
        else
            return lhs.second < rhs.second;
    }
};

struct circle
{
    int x, y, r;
};

circle circles[300010];

void firstSubtask(int n)
{
    std::set< std::pair<int, int>, compare > set;
    int visited[300010] = { 0 };
    int x[300010], y[300010], r[300010];
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> x[i] >> y[i] >> r[i];
        set.insert(std::make_pair(r[i], i));
    }

    while (set.empty() == false)
    {
        std::pair<int, int> p = *set.begin();
        set.erase(set.begin());
        int xs = x[p.second], ys = y[p.second], rs = r[p.second];
        visited[p.second] = p.second;

        for (auto it = set.begin(); it != set.end();)
        {
            std::pair<int, int> sec = *it;
            int xq = x[sec.second], yq = y[sec.second], rq = r[sec.second];
            long double dist = sqrt(sqr(xq * 1.0 - xs * 1.0) + sqr(yq * 1.0 - ys * 1.0));

  //          std::cout << p.second << " " << sec.second << " " << dist << " " << rq * 1.0 + rs * 1.0 << "\n";

            if (dist <= rq * 1.0 + rs * 1.0)
            {
                visited[sec.second] = p.second;
                it = set.erase(it);
            }
            else
            {
                ++it;
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        std::cout << visited[i] << " ";
    }
}

void secondSubtask(int n)
{
    std::set< std::pair<int, int>, compare > radiuses;
    std::set< std::pair<int, int> > right, left;
    for (int i = 1; i <= n; ++i)
    {
        radiuses.insert(std::make_pair(circles[i].r, i));
        right.insert(std::make_pair(circles[i].x + circles[i].r, i));
        left.insert(std::make_pair(circles[i].x - circles[i].r, i));
    }

    int visited[300010] = { 0 };
    while (radiuses.empty() == false)
    {
        auto radius = radiuses.begin();
        std::pair<int, int> boss = *radius;
        radiuses.erase(radius);

        visited[boss.second] = boss.second;

        auto it = right.find(std::make_pair(circles[boss.second].x + circles[boss.second].r, boss.second));
        int leftCheck = circles[boss.second].x - circles[boss.second].r;
        int rightCheck = circles[boss.second].x + circles[boss.second].r;

        while (it != right.begin())
        {
            --it;
            std::pair<int, int> under = *it;

    //        std::cout << boss.second << " " << boss.first << " " << under.first << " " << under.second << " " << leftCheck << "\n";
            if (under.first >= leftCheck)
            {
                it = right.erase(it);
                left.erase(std::make_pair(circles[under.second].x - circles[under.second].r, under.second));
                visited[under.second] = boss.second;
                radiuses.erase(std::make_pair(circles[under.second].r, under.second));
            }
            else
                break;
        }

        right.erase(std::make_pair(circles[boss.second].x + circles[boss.second].r, boss.second));
        it = left.find(std::make_pair(circles[boss.second].x - circles[boss.second].r, boss.second));
        ++it;

        while (it != left.end())
        {
            std::pair<int, int> under = *it;

  //          std::cout << boss.second << " " << boss.first << " " << under.first << " " << under.second << " " << rightCheck << "\n";
            if (under.first <= rightCheck)
            {
                it = left.erase(it);
                right.erase(std::make_pair(circles[under.second].x + circles[under.second].r, under.second));
                visited[under.second] = boss.second;
                radiuses.erase(std::make_pair(circles[under.second].r, under.second));
            }
            else
                break;
        }

        left.erase(left.find(std::make_pair(circles[boss.second].x - circles[boss.second].r, boss.second)));
    }


    for (int i = 1; i <= n; ++i)
    {
        std::cout << visited[i] << " ";
    }
}

void thirdSubtask(int n)
{
    std::set< std::pair<int, int>, compare > radiuses;
    std::set< std::pair<int, int> > xses, yses;

    int visited[300010] = { 0 };
    for (int i = 1; i <= n; ++i)
    {
        radiuses.insert(std::make_pair(circles[i].r, i));
        xses.insert(std::make_pair(circles[i].x, i));
        yses.insert(std::make_pair(circles[i].y, i));
    }


    while (radiuses.empty() == false)
    {
        auto radius = radiuses.begin();
        std::pair<int, int> boss = *radius;
        radiuses.erase(radius);

        visited[boss.second] = boss.second;

        auto it = xses.find(std::make_pair(circles[boss.second].x, boss.second));
        if (it != xses.begin())
        {
            --it;
            std::pair<int, int> next = *it;
            long double dist = sqrt(sqr(circles[boss.second].x - circles[next.second].x) + sqr(circles[boss.second].y - circles[next.second].y));

            if (dist <= circles[boss.second].r + circles[next.second].r)
            {
                visited[next.second] = boss.second;
                radiuses.erase(std::make_pair(circles[next.second].r, next.second));
                xses.erase(it);
                yses.erase(std::make_pair(circles[next.second].y, next.second));
            }
        }

        it = xses.find(std::make_pair(circles[boss.second].x, boss.second));
        ++it;
        if (it != xses.end())
        {
            std::pair<int, int> next = *it;
            long double dist = sqrt(sqr(circles[boss.second].x - circles[next.second].x) + sqr(circles[boss.second].y - circles[next.second].y));

            if (dist <= circles[boss.second].r + circles[next.second].r)
            {
                visited[next.second] = boss.second;
                radiuses.erase(std::make_pair(circles[next.second].r, next.second));
                xses.erase(it);
                yses.erase(std::make_pair(circles[next.second].y, next.second));
            }
        }
        xses.erase(std::make_pair(circles[boss.second].x, boss.second));

        it = yses.find(std::make_pair(circles[boss.second].y, boss.second));
        if (it != yses.begin())
        {
            --it;
            std::pair<int, int> next = *it;
            long double dist = sqrt(sqr(circles[boss.second].x - circles[next.second].x) + sqr(circles[boss.second].y - circles[next.second].y));

            if (dist <= circles[boss.second].r + circles[next.second].r)
            {
                visited[next.second] = boss.second;
                radiuses.erase(std::make_pair(circles[next.second].r, next.second));
                yses.erase(it);
                xses.erase(std::make_pair(circles[next.second].x, next.second));
            }
        }

        it = yses.find(std::make_pair(circles[boss.second].y, boss.second));
        ++it;
        if (it != yses.end())
        {
            std::pair<int, int> next = *it;
            long double dist = sqrt(sqr(circles[boss.second].x - circles[next.second].x) + sqr(circles[boss.second].y - circles[next.second].y));

            if (dist <= circles[boss.second].r + circles[next.second].r)
            {
                visited[next.second] = boss.second;
                radiuses.erase(std::make_pair(circles[next.second].r, next.second));
                yses.erase(it);
                xses.erase(std::make_pair(circles[next.second].x, next.second));
            }
        }

        yses.erase(std::make_pair(circles[boss.second].y, boss.second));
    }

    for (int i = 1; i <= n; ++i)
    {
        std::cout << visited[i] << " ";
    }
}

int main()
{
    int n;
    std::cin >> n;

    if (n <= 1)
    {
        firstSubtask(n);
        return 0;
    }

    bool flag = true;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> circles[i].x >> circles[i].y >> circles[i].r;

        if (circles[i].y != 0)
        {
            flag = false;
        }
    }

    if (flag)
    {
        secondSubtask(n);
        return 0;
    }

    thirdSubtask(n);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1636 KB Output is correct
3 Correct 3 ms 1688 KB Output is correct
4 Correct 3 ms 1704 KB Output is correct
5 Correct 3 ms 1704 KB Output is correct
6 Incorrect 3 ms 1704 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2293 ms 49612 KB Output is correct
2 Correct 2093 ms 49612 KB Output is correct
3 Correct 2060 ms 49612 KB Output is correct
4 Correct 2166 ms 49684 KB Output is correct
5 Correct 1643 ms 49684 KB Output is correct
6 Correct 1738 ms 49684 KB Output is correct
7 Correct 1908 ms 49684 KB Output is correct
8 Correct 1578 ms 49684 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 49684 KB Output is correct
2 Incorrect 644 ms 49684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2017 ms 49684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1636 KB Output is correct
3 Correct 3 ms 1688 KB Output is correct
4 Correct 3 ms 1704 KB Output is correct
5 Correct 3 ms 1704 KB Output is correct
6 Incorrect 3 ms 1704 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 4 ms 1636 KB Output is correct
3 Correct 3 ms 1688 KB Output is correct
4 Correct 3 ms 1704 KB Output is correct
5 Correct 3 ms 1704 KB Output is correct
6 Incorrect 3 ms 1704 KB Output isn't correct
7 Halted 0 ms 0 KB -