답안 #52628 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52628	2018-06-26T09:57:36 Z	Kubalionzzale	원 고르기 (APIO18_circle_selection)	C++14	7 / 100	3000 ms	43172 KB

circle_selection

#include <iostream>
#include <set>
#include <math.h>
#include <algorithm>
#include <functional>

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

int main()
{
    int n;
    std::cin >> 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] << " ";
    }
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1528 KB	Output is correct
2	Correct	4 ms	1644 KB	Output is correct
3	Correct	3 ms	1644 KB	Output is correct
4	Correct	4 ms	1644 KB	Output is correct
5	Correct	4 ms	1648 KB	Output is correct
6	Correct	3 ms	1656 KB	Output is correct
7	Correct	3 ms	1660 KB	Output is correct
8	Correct	4 ms	1664 KB	Output is correct
9	Correct	3 ms	1716 KB	Output is correct
10	Correct	3 ms	1776 KB	Output is correct
11	Correct	3 ms	1784 KB	Output is correct
12	Correct	3 ms	1916 KB	Output is correct
13	Correct	4 ms	1916 KB	Output is correct
14	Correct	3 ms	1916 KB	Output is correct
15	Correct	4 ms	1916 KB	Output is correct
16	Correct	5 ms	1932 KB	Output is correct
17	Correct	6 ms	1964 KB	Output is correct
18	Correct	5 ms	1992 KB	Output is correct
19	Correct	18 ms	2280 KB	Output is correct
20	Correct	18 ms	2576 KB	Output is correct
21	Correct	13 ms	2628 KB	Output is correct
22	Correct	300 ms	2792 KB	Output is correct
23	Correct	281 ms	3028 KB	Output is correct
24	Correct	301 ms	3204 KB	Output is correct
25	Correct	295 ms	3276 KB	Output is correct
26	Correct	360 ms	3480 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	888 ms	22940 KB	Output is correct
2	Correct	910 ms	22940 KB	Output is correct
3	Correct	887 ms	29264 KB	Output is correct
4	Correct	931 ms	36360 KB	Output is correct
5	Execution timed out	3041 ms	38964 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1528 KB	Output is correct
2	Correct	4 ms	1644 KB	Output is correct
3	Correct	3 ms	1644 KB	Output is correct
4	Correct	4 ms	1644 KB	Output is correct
5	Correct	4 ms	1648 KB	Output is correct
6	Correct	3 ms	1656 KB	Output is correct
7	Correct	3 ms	1660 KB	Output is correct
8	Correct	4 ms	1664 KB	Output is correct
9	Correct	3 ms	1716 KB	Output is correct
10	Correct	3 ms	1776 KB	Output is correct
11	Correct	3 ms	1784 KB	Output is correct
12	Correct	3 ms	1916 KB	Output is correct
13	Correct	4 ms	1916 KB	Output is correct
14	Correct	3 ms	1916 KB	Output is correct
15	Correct	4 ms	1916 KB	Output is correct
16	Correct	5 ms	1932 KB	Output is correct
17	Correct	6 ms	1964 KB	Output is correct
18	Correct	5 ms	1992 KB	Output is correct
19	Correct	18 ms	2280 KB	Output is correct
20	Correct	18 ms	2576 KB	Output is correct
21	Correct	13 ms	2628 KB	Output is correct
22	Correct	300 ms	2792 KB	Output is correct
23	Correct	281 ms	3028 KB	Output is correct
24	Correct	301 ms	3204 KB	Output is correct
25	Correct	295 ms	3276 KB	Output is correct
26	Correct	360 ms	3480 KB	Output is correct
27	Correct	26 ms	41628 KB	Output is correct
28	Correct	28 ms	41628 KB	Output is correct
29	Correct	27 ms	41628 KB	Output is correct
30	Correct	1678 ms	41628 KB	Output is correct
31	Correct	1571 ms	41628 KB	Output is correct
32	Correct	1529 ms	41628 KB	Output is correct
33	Correct	304 ms	41628 KB	Output is correct
34	Correct	340 ms	41628 KB	Output is correct
35	Correct	310 ms	41628 KB	Output is correct
36	Execution timed out	3043 ms	43172 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1528 KB	Output is correct
2	Correct	4 ms	1644 KB	Output is correct
3	Correct	3 ms	1644 KB	Output is correct
4	Correct	4 ms	1644 KB	Output is correct
5	Correct	4 ms	1648 KB	Output is correct
6	Correct	3 ms	1656 KB	Output is correct
7	Correct	3 ms	1660 KB	Output is correct
8	Correct	4 ms	1664 KB	Output is correct
9	Correct	3 ms	1716 KB	Output is correct
10	Correct	3 ms	1776 KB	Output is correct
11	Correct	3 ms	1784 KB	Output is correct
12	Correct	3 ms	1916 KB	Output is correct
13	Correct	4 ms	1916 KB	Output is correct
14	Correct	3 ms	1916 KB	Output is correct
15	Correct	4 ms	1916 KB	Output is correct
16	Correct	5 ms	1932 KB	Output is correct
17	Correct	6 ms	1964 KB	Output is correct
18	Correct	5 ms	1992 KB	Output is correct
19	Correct	18 ms	2280 KB	Output is correct
20	Correct	18 ms	2576 KB	Output is correct
21	Correct	13 ms	2628 KB	Output is correct
22	Correct	300 ms	2792 KB	Output is correct
23	Correct	281 ms	3028 KB	Output is correct
24	Correct	301 ms	3204 KB	Output is correct
25	Correct	295 ms	3276 KB	Output is correct
26	Correct	360 ms	3480 KB	Output is correct
27	Correct	888 ms	22940 KB	Output is correct
28	Correct	910 ms	22940 KB	Output is correct
29	Correct	887 ms	29264 KB	Output is correct
30	Correct	931 ms	36360 KB	Output is correct
31	Execution timed out	3041 ms	38964 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #52628

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 0 / 12.0

Subtask #3 0 / 15.0

Subtask #4 0 / 23.0

Subtask #5 0 / 30.0

Subtask #6 0 / 13.0

Subtask #1
7.0 / 7.0

Subtask #2
0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0