Submission #982354

#	Time	Username	Problem	Language	Result	Execution time	Memory
982354		Muhammad_Aneeq	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3078 ms	37152 KiB

circle_selection

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int man(pair<int,int>a,pair<int,int>b)
{
    return ((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
inline void solve()
{
    int n;
    cin>>n;
    pair<int,int>a[n];
    bool w=0;
    set<pair<int,int>>s;
    int ra[n]={};
    for (int i=0;i<n;i++)
    {
        int x,y,r;
        cin>>x>>y>>r;
        a[i]={x,y};
        if (y!=0)
            w=1;
        s.insert({-r,i});
        ra[i]=r;
    }  
    if (w==0)
    {
        vector<pair<int,int>>f;
        for (int i=0;i<n;i++)
            f.push_back({a[i].first,i});
        s={};
        sort(begin(f),end(f));
        for (int i=0;i<n;i++)
            s.insert({-ra[f[i].second],i});
        bool vis[n]={};
        int ans[n]={};
        while (s.size())
        {
            int r=(*begin(s)).first,i=(*begin(s)).second;
            s.erase(*begin(s));
            ans[i]=f[i].second;
            vis[i]=1;
            vector<pair<int,int>>z;
            for (int j=i+1;j<n;j++)
            {
                if (vis[j])
                    break;
                int r1=ra[f[j].second];
                int dis=man(a[f[i].second],a[f[j].second]);
                if (dis<=((r+r1)*(r+r1)))
                    z.push_back({r1,j});
                else
                    break;
            }
            for (int j=i-1;j>=0;j--)
            {
                if (vis[j])
                    break;
                int r1=ra[f[j].second];
                int dis=man(a[f[i].second],a[f[j].second]);
                if (dis<=((r+r1)*(r+r1)))
                    z.push_back({r1,j});
                else
                    break;
            }
            for (auto j:z)
            {
                ans[f[j.second].second]=f[i].second;
                vis[f[j.second].second]=1;
                s.erase(j);
            }
        }
        for (auto i:ans)
            cout<<i+1<<' ';
        cout<<endl;
        return;
    }
    else
    {
        int ans[n]={};
        while (s.size())
        {
            int r=(*begin(s)).first,i=(*begin(s)).second;
            s.erase(*begin(s));
            ans[i]=i;
            vector<pair<int,int>>z;
            for (auto [r1,j]:s)
            {
                int dis=man(a[i],a[j]);
                if (dis<=((r+r1)*(r+r1)))
                    z.push_back({r1,j});
                if (z.size()&&n>5000)
                    break;
            }
            for (auto j:z)
            {
                ans[j.second]=i;
                s.erase(j);
            }
        }
        for (auto i:ans)
            cout<<i+1<<' ';
        cout<<endl;
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

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