제출 #407459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407459		RGBB	원 고르기 (APIO18_circle_selection)	C++14	100 / 100	2667 ms	388484 KiB

circle_selection

#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int>pp;
const int MAXN=300000;
bool vis[MAXN];
int n,cr,outp[MAXN],inp[MAXN][3];
pp take[MAXN];
gp_hash_table<int,gp_hash_table<int,vector<int>>>plane;
void initialize(int cx,int cy){
    if(plane.find(cx)==plane.end()){
        gp_hash_table<int,vector<int>>temp;
        plane[cx]=temp;
    }
    if(plane[cx].find(cy)==plane[cx].end()){
        vector<int>temp;
        plane[cx][cy]=temp;
    }
}
void create(){
    plane.clear();
    for(pp i:take){
        if(vis[i.second])continue;
        int cx=(inp[i.second][0]>>cr);
        int cy=(inp[i.second][1]>>cr);
        initialize(cx,cy);
        plane[cx][cy].push_back(i.second);
    }
}
ll xx,yy,rr;
bool intersect(int a,int b){
    xx=inp[a][0]-inp[b][0];
    yy=inp[a][1]-inp[b][1];
    rr=inp[a][2]+inp[b][2];
    if(xx*xx+yy*yy<=rr*rr)return true;
    return false;
}
void calc(int c){
    int cx=(inp[c][0]>>cr);
    int cy=(inp[c][1]>>cr);
    for(int i=-1;i<=1;i++){
        for(int y=-1;y<=1;y++){
            if(plane.find(cx+i)==plane.end()||plane[cx+i].find(cy+y)==plane[cx+i].end())continue;
            for(int i:plane[cx+i][cy+y]){
                if(!vis[i]&&intersect(i,c)){
                    outp[i]=c;
                    vis[i]=true;
                }
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(vis,false,sizeof(vis));
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>inp[i][0]>>inp[i][1]>>inp[i][2];
        take[i]={-inp[i][2],i};
    }
    sort(take,take+n);
    cr=30;
    create();
    bool change=false;
    for(int i=0;i<n;i++){
        if(vis[take[i].second])continue;
        while(-take[i].first<(double)(1<<(cr-2))/sqrt(2)){
            cr--;
            change=true;
        }
        if(change)create();
        change=false;
        calc(take[i].second);
    }
    for(int i=0;i<n-1;i++)cout<<outp[i]+1<<" ";
    cout<<outp[n-1]+1<<"\n";
}

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