Submission #1178490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178490		huydarwin	Circle selection (APIO18_circle_selection)	C++20	34 / 100	806 ms	125772 KiB

circle_selection

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ii pii
#define fi first
#define sc second
#define ll long long
#define pll pair<ll,ll>
#define ill pair<int,ll>
#define lli pair<ll,int>
#define inf 2000000000
#define INF inf
#define endl "\n"
#define pb push_back
#define eb emplace_back
#define llinf (ll)1e18
#define LLINF llinf
#define maxn 300005
#define maxm
#define task ""
using namespace std;

int n;
struct{
    ll x,y,r;
} a[maxn];

ll dist2(int u,int v){
    ll diffx = (a[u].x - a[v].x) * (a[u].x - a[v].x);
    ll diffy = (a[u].y - a[v].y) * (a[u].y - a[v].y);
    return diffx + diffy;
}

double dist(int u,int v){
    return sqrt(dist2(u,v));
}

bool intersect(int u,int v){
    return dist2(u,v) <= (a[u].r + a[v].r) * (a[u].r + a[v].r);
}

vector<int> adj[maxn];
int cnt;
int vt[maxn];
int cl[maxn];
int c[maxn];

void sub1(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            if(intersect(i,j)) adj[i].pb(j);
        }
    }
    for(int i=1;i<=n;i++) vt[i]=i;
    sort(vt+1,vt+n+1,[](auto u,auto v){
        return a[u].r > a[v].r;
    });
    for(int i=1;i<=n;i++) cl[i]=1;
    cnt=n;
    int j=1;
    while(cnt>0){
        while(j<=n && cl[vt[j]] == 0) j++;
        cnt--;
        cl[vt[j]]=0;
        c[vt[j]] = vt[j];
        for(auto u: adj[vt[j]]) if(cl[u] == 1){
            cnt--;
            cl[u] = 0;
            c[u] = vt[j];
        }
    }
    for(int i=1;i<=n;i++) cout<<c[i]<<" "; cout<<endl;
}

bool checksub2(){
    for(int i=1;i<=n;i++) if(a[i].y != 0) return false;
    return true;
}

multiset<lli> bankinh,val;
int cnt2=0;
int luu2[2*maxn];

void sub2(){
    for(int i=1;i<=n;i++){
        bankinh.insert({-a[i].r, i});
        val.insert({a[i].x - a[i].r, i});
        val.insert({a[i].x + a[i].r, i});
    }
    while(!bankinh.empty()){
        int u=bankinh.begin()->sc;

        bankinh.erase({-a[u].r, u});
        val.erase({a[u].x - a[u].r, u});
        val.erase({a[u].x + a[u].r, u});
        c[u] = u;

        cnt2=0;
        auto it = val.lower_bound({a[u].x - a[u].r, 0});
        for(it;; it++){
            if(it==val.end()) break;
            if(it->fi > a[u].x + a[u].r) break;
            luu2[++cnt2] = it->sc;
        }

        for(int i=1;i<=cnt2;i++){
            int v = luu2[i];
            if(c[v] != 0) continue;
            bankinh.erase({-a[v].r, v});
            val.erase({a[v].x - a[v].r, v});
            val.erase({a[v].x + a[v].r, v});
            c[v] = u;
        }
    }
    for(int i=1;i<=n;i++) cout<<c[i]<<" "; cout<<endl;
}

set<lli> marker;
pair<lli,int> value[2*maxn];

void sub3(){
    for(int i=1;i<=n;i++){
        value[i] = {{a[i].y + a[i].r, i}, 1};
        value[i+n] = {{a[i].y - a[i].r, i}, 0};
    }
    for(int i=1;i<=n;i++) c[i]=i;
    sort(value+1, value+2*n+1);
    reverse(value+1, value+2*n+1);
    for(int i=1;i<=2*n;i++){
        int id = value[i].fi.sc;
        if(value[i].sc == 1){
            marker.insert({a[id].x, id});
            auto it = marker.lower_bound({a[id].x, id});
            if (it != marker.begin()) {
                auto itprev = marker.lower_bound({a[id].x, id});
                --itprev;
                int idprev = itprev -> sc;
                if (intersect(id, idprev)) {
                    if (a[id].r > a[idprev].r) c[idprev] = id;
                    else if (a[id].r < a[idprev].r) c[id] = idprev;
                    else if (id < idprev) c[idprev] = id;
                    else if (id > idprev) c[id] = idprev;
                }
            }
            auto ittmp = it;
            ittmp++;
            if (ittmp != marker.end()) {
                auto itnext = marker.lower_bound({a[id].x, id});
                ++itnext;
                int idnext = itnext -> sc;
                if (intersect(id, idnext)) {
                    if (a[id].r > a[idnext].r) c[idnext] = id;
                    else if (a[id].r < a[idnext].r) c[id] = idnext;
                    else if (id < idnext) c[idnext] = id;
                    else if (id > idnext) c[id] = idnext;
                }
            }
        }
        else{
            auto it = marker.lower_bound({a[id].x, id});
            auto ittmp = it;
            ittmp++;
            if (it != marker.begin() && ittmp != marker.end()) {
                auto itprev = marker.lower_bound({a[id].x, id});
                --itprev;
                int idprev = itprev -> sc;

                auto itnext = marker.lower_bound({a[id].x, id});
                ++itnext;
                int idnext = itnext -> sc;

                if (intersect(idprev, idnext)) {
                    if (a[idprev].r > a[idnext].r) c[idnext] = idprev;
                    else if (a[idprev].r < a[idnext].r) c[idprev] = idnext;
                    else if (idprev < idnext) c[idnext] = idprev;
                    else if (idprev > idnext) c[idprev] = idnext;
                }
            }
            marker.erase({a[id].x, id});
        }
    }
    for(int i=1;i<=n;i++) cout<<c[i]<<" "; cout<<endl;
}

int main(){
    if (fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].r;
    if(n<=5000) sub1();
    else if(checksub2()) sub2();
    else sub3();

    return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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