oj.uz

Submission #742069

# Submission time Handle Problem Language Result Execution time Memory
742069 2023-05-15T14:23:13 Z speedyArda Circle selection (APIO18_circle_selection) C++14
19 / 100
 900 ms 48172 KB 
#include "bits/stdc++.h"
#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
using namespace std;
const int MAXN = 3e5+5;
vector< pair < pair<int, int>, pair<int, int> > > circles;
vector<int> ans(MAXN, 0);
int id[MAXN];
bool cmp(int &a, int &b)
{
    if(circles[a].second.first != circles[b].second.first)
        return circles[a].second.first > circles[b].second.first;
    return circles[a].second.second < circles[b].second.second;
}

/*struct cmpset {
    bool operator()(pair<pair<int, int> , int> &a, pair<pair<int, int> , int> &b)
    {
        if(a.first.first != b.first.first)
            return a < b;
        if(a.first.second != b.first.second)
            return a.first.second > b.first.second;
        return a.second < b.second;
    }
};*/
int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int maxy = -1e9;
    for(int i = 0; i < n; i++)
    {
        int x, y, r;

        cin >> x >> y >> r;
        maxy = max(maxy, y);
        circles.push_back({{x, y}, {r, i}});
        id[i] = i;
    }

    sort(id, id + n, cmp);
    //cout << "s\n";
    if(n <= 5e3 && maxy != 0)
    {
        for(int idx = 0; idx < n; idx++)
        {
            int i = id[idx];
            if(ans[circles[i].second.second] != 0)
                continue;
            //cout << circles[i].second.second << "\n";
            ans[circles[i].second.second] = circles[i].second.second + 1;
            for(int a = 0; a < n; a++)
            {
                if(ans[circles[a].second.second] == 0)
                {
                    long double dist = sqrt(pow(abs(circles[i].first.first - circles[a].first.first), 2) + pow(abs(circles[i].first.second - circles[a].first.second), 2));
                    if(dist <= circles[i].second.first + circles[a].second.first)
                        ans[circles[a].second.second] = circles[i].second.second + 1;
                }
            }
        }
    } else 
    {
        multiset< pair<int , int> > elems;
        for(int i = 0; i < n; i++)
        {
            elems.insert({circles[i].first.first - circles[i].second.first, circles[i].second.second});
            elems.insert({circles[i].first.first + circles[i].second.first, circles[i].second.second});
        }
        for(int idx = 0; idx < n; idx++)
        {
            int i = id[idx];
            if(ans[circles[i].second.second] != 0)
                continue;
            //cout << circles[i].second.second << "\n";
            vector<int> toerase;
           // auto it = elems.lower_bound({{circles[i].first.first - circles[i].second.first, circles[i].first.first + circles[i].second.first},  circles[i].second.second});
            auto it = elems.lower_bound({circles[i].first.first + circles[i].second.first + 1, 0});
            it--;
            while((*it).first >= circles[i].first.first - circles[i].second.first)
            {
                toerase.push_back((*it).second);
                if(it == elems.begin()) 
                    break;
                it--;
            }

            for(int e : toerase)
            {
                //cout << i << " " << e << "\n";
                if(ans[circles[e].second.second] == 0) {
                    ans[circles[e].second.second] = circles[i].second.second + 1;
                    elems.erase(elems.find({circles[e].first.first - circles[e].second.first,  circles[e].second.second}));
                    elems.erase(elems.find({circles[e].first.first + circles[e].second.first, circles[e].second.second}));
                }
            }
        }
    }

    for(int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << "\n";
}

Compilation message

circle_selection.cpp:2:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
circle_selection.cpp:2:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
circle_selection.cpp:2:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
circle_selection.cpp:2:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
circle_selection.cpp:8:24: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    8 | bool cmp(int &a, int &b)
      |                        ^
circle_selection.cpp:8:24: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circle_selection.cpp:8:24: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circle_selection.cpp:8:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circle_selection.cpp:25:10: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   25 | int main()
      |          ^
circle_selection.cpp:25:10: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circle_selection.cpp:25:10: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circle_selection.cpp:25:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1520 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1508 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 2 ms 1568 KB Output is correct
17 Correct 2 ms 1492 KB Output is correct
18 Correct 2 ms 1492 KB Output is correct
19 Correct 4 ms 1876 KB Output is correct
20 Correct 4 ms 1876 KB Output is correct
21 Correct 4 ms 1876 KB Output is correct
22 Correct 103 ms 1856 KB Output is correct
23 Correct 103 ms 1876 KB Output is correct
24 Correct 103 ms 1876 KB Output is correct
25 Correct 120 ms 1876 KB Output is correct
26 Correct 103 ms 1864 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 48092 KB Output is correct
2 Correct 883 ms 46292 KB Output is correct
3 Correct 889 ms 47396 KB Output is correct
4 Correct 900 ms 48172 KB Output is correct
5 Correct 640 ms 42128 KB Output is correct
6 Correct 649 ms 42244 KB Output is correct
7 Correct 593 ms 42244 KB Output is correct
8 Correct 582 ms 42288 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1520 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1508 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 2 ms 1568 KB Output is correct
17 Correct 2 ms 1492 KB Output is correct
18 Correct 2 ms 1492 KB Output is correct
19 Correct 4 ms 1876 KB Output is correct
20 Correct 4 ms 1876 KB Output is correct
21 Correct 4 ms 1876 KB Output is correct
22 Correct 103 ms 1856 KB Output is correct
23 Correct 103 ms 1876 KB Output is correct
24 Correct 103 ms 1876 KB Output is correct
25 Correct 120 ms 1876 KB Output is correct
26 Correct 103 ms 1864 KB Output is correct
27 Incorrect 14 ms 3120 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1520 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1508 KB Output is correct
9 Correct 1 ms 1516 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 2 ms 1568 KB Output is correct
17 Correct 2 ms 1492 KB Output is correct
18 Correct 2 ms 1492 KB Output is correct
19 Correct 4 ms 1876 KB Output is correct
20 Correct 4 ms 1876 KB Output is correct
21 Correct 4 ms 1876 KB Output is correct
22 Correct 103 ms 1856 KB Output is correct
23 Correct 103 ms 1876 KB Output is correct
24 Correct 103 ms 1876 KB Output is correct
25 Correct 120 ms 1876 KB Output is correct
26 Correct 103 ms 1864 KB Output is correct
27 Correct 871 ms 48092 KB Output is correct
28 Correct 883 ms 46292 KB Output is correct
29 Correct 889 ms 47396 KB Output is correct
30 Correct 900 ms 48172 KB Output is correct
31 Correct 640 ms 42128 KB Output is correct
32 Correct 649 ms 42244 KB Output is correct
33 Correct 593 ms 42244 KB Output is correct
34 Correct 582 ms 42288 KB Output is correct
35 Correct 1 ms 1492 KB Output is correct
36 Incorrect 164 ms 16168 KB Output isn't correct
37 Halted 0 ms 0 KB -