제출 #1177897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177897		huydarwin	원 고르기 (APIO18_circle_selection)	C++20	7 / 100	473 ms	125632 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[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!=val.end() && it->fi <= a[u].x + a[u].r; it++){
            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;
}

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();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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