답안 #49427 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49427	2018-05-28T17:02:54 Z	gs13105	원 고르기 (APIO18_circle_selection)	C++17	19 / 100	1210 ms	38028 KB

circle_selection

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

struct cir
{
    int x, y, r, i;
    bool operator <(const cir &a) const
    {
        return r != a.r ? r > a.r : i < a.i;
    }
};

cir arr[300010];
int num[300010];
int res[300010];

bool inter(const cir &a, const cir &b)
{
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y) <= 1LL * (a.r + b.r) * (a.r + b.r);
}

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int n, i, j;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
    {
        int x, y, r;
        scanf("%d%d%d", &x, &y, &r);
        arr[i] = { x, y, r, i };
    }

    sort(arr + 1, arr + n + 1);

    if(n <= 5000)
    {
        for(i = 1; i <= n; i++)
            if(!num[i])
                for(j = 1; j <= n; j++)
                    if(!num[j] && inter(arr[i], arr[j]))
                        num[j] = arr[i].i;

        for(i = 1; i <= n; i++)
            res[arr[i].i] = num[i];

        for(i = 1; i <= n; i++)
            printf("%d ", res[i]);
        return 0;
    }

    bool st2 = 1;
    for(i = 1; i <= n; i++)
    {
        if(arr[i].y != 0)
        {
            st2 = 0;
            break;
        }
    }

    if(st2)
    {
        set<pair<int, int>> s;
        for(i = 1; i <= n; i++)
        {
            s.insert({ arr[i].x - arr[i].r, i });
            s.insert({ arr[i].x + arr[i].r, i });
        }

        for(i = 1; i <= n; i++)
        {
            if(num[i])
                continue;

            auto it = s.lower_bound({ arr[i].x - arr[i].r, -1 });
            while(it != s.end() && it->first <= arr[i].x + arr[i].r)
            {
                int x = it->second;
                if(!num[x])
                    num[x] = arr[i].i;

                it++;
                s.erase(prev(it));
            }
        }

        for(i = 1; i <= n; i++)
            res[arr[i].i] = num[i];

        for(i = 1; i <= n; i++)
            printf("%d ", res[i]);
        return 0;
    }

    return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
circle_selection.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	500 KB	Output is correct
4	Correct	2 ms	524 KB	Output is correct
5	Correct	2 ms	600 KB	Output is correct
6	Correct	2 ms	696 KB	Output is correct
7	Correct	2 ms	696 KB	Output is correct
8	Correct	2 ms	696 KB	Output is correct
9	Correct	3 ms	696 KB	Output is correct
10	Correct	3 ms	696 KB	Output is correct
11	Correct	2 ms	696 KB	Output is correct
12	Correct	2 ms	696 KB	Output is correct
13	Correct	2 ms	696 KB	Output is correct
14	Correct	2 ms	696 KB	Output is correct
15	Correct	3 ms	696 KB	Output is correct
16	Correct	3 ms	696 KB	Output is correct
17	Correct	3 ms	696 KB	Output is correct
18	Correct	3 ms	696 KB	Output is correct
19	Correct	5 ms	724 KB	Output is correct
20	Correct	5 ms	724 KB	Output is correct
21	Correct	6 ms	736 KB	Output is correct
22	Correct	44 ms	752 KB	Output is correct
23	Correct	47 ms	812 KB	Output is correct
24	Correct	44 ms	828 KB	Output is correct
25	Correct	54 ms	828 KB	Output is correct
26	Correct	45 ms	828 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1141 ms	37936 KB	Output is correct
2	Correct	1065 ms	38028 KB	Output is correct
3	Correct	1156 ms	38028 KB	Output is correct
4	Correct	1210 ms	38028 KB	Output is correct
5	Correct	1092 ms	38028 KB	Output is correct
6	Correct	981 ms	38028 KB	Output is correct
7	Correct	958 ms	38028 KB	Output is correct
8	Correct	839 ms	38028 KB	Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	155 ms	38028 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	500 KB	Output is correct
4	Correct	2 ms	524 KB	Output is correct
5	Correct	2 ms	600 KB	Output is correct
6	Correct	2 ms	696 KB	Output is correct
7	Correct	2 ms	696 KB	Output is correct
8	Correct	2 ms	696 KB	Output is correct
9	Correct	3 ms	696 KB	Output is correct
10	Correct	3 ms	696 KB	Output is correct
11	Correct	2 ms	696 KB	Output is correct
12	Correct	2 ms	696 KB	Output is correct
13	Correct	2 ms	696 KB	Output is correct
14	Correct	2 ms	696 KB	Output is correct
15	Correct	3 ms	696 KB	Output is correct
16	Correct	3 ms	696 KB	Output is correct
17	Correct	3 ms	696 KB	Output is correct
18	Correct	3 ms	696 KB	Output is correct
19	Correct	5 ms	724 KB	Output is correct
20	Correct	5 ms	724 KB	Output is correct
21	Correct	6 ms	736 KB	Output is correct
22	Correct	44 ms	752 KB	Output is correct
23	Correct	47 ms	812 KB	Output is correct
24	Correct	44 ms	828 KB	Output is correct
25	Correct	54 ms	828 KB	Output is correct
26	Correct	45 ms	828 KB	Output is correct
27	Incorrect	8 ms	38028 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	500 KB	Output is correct
4	Correct	2 ms	524 KB	Output is correct
5	Correct	2 ms	600 KB	Output is correct
6	Correct	2 ms	696 KB	Output is correct
7	Correct	2 ms	696 KB	Output is correct
8	Correct	2 ms	696 KB	Output is correct
9	Correct	3 ms	696 KB	Output is correct
10	Correct	3 ms	696 KB	Output is correct
11	Correct	2 ms	696 KB	Output is correct
12	Correct	2 ms	696 KB	Output is correct
13	Correct	2 ms	696 KB	Output is correct
14	Correct	2 ms	696 KB	Output is correct
15	Correct	3 ms	696 KB	Output is correct
16	Correct	3 ms	696 KB	Output is correct
17	Correct	3 ms	696 KB	Output is correct
18	Correct	3 ms	696 KB	Output is correct
19	Correct	5 ms	724 KB	Output is correct
20	Correct	5 ms	724 KB	Output is correct
21	Correct	6 ms	736 KB	Output is correct
22	Correct	44 ms	752 KB	Output is correct
23	Correct	47 ms	812 KB	Output is correct
24	Correct	44 ms	828 KB	Output is correct
25	Correct	54 ms	828 KB	Output is correct
26	Correct	45 ms	828 KB	Output is correct
27	Correct	1141 ms	37936 KB	Output is correct
28	Correct	1065 ms	38028 KB	Output is correct
29	Correct	1156 ms	38028 KB	Output is correct
30	Correct	1210 ms	38028 KB	Output is correct
31	Correct	1092 ms	38028 KB	Output is correct
32	Correct	981 ms	38028 KB	Output is correct
33	Correct	958 ms	38028 KB	Output is correct
34	Correct	839 ms	38028 KB	Output is correct
35	Correct	2 ms	38028 KB	Output is correct
36	Incorrect	63 ms	38028 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

답안 #49427

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.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
12.0 / 12.0

Subtask #3
0 / 15.0

Subtask #4
0 / 23.0

Subtask #5
0 / 30.0

Subtask #6
0 / 13.0