제출 #439264

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

circle_selection

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pp;
const int MAXN=300000;
const int rnd=1e9+7;
const int base=4405829;
bool vis[MAXN];
int n,cr,outp[MAXN],inp[MAXN][3];
pp take[MAXN];
vector<int>plane[base],reset;
int cmp(int a,int b){
    return abs((a*rnd+b)%base);
}
void create(){
    for(int i:reset)plane[i].clear();
    reset.clear();
    for(pp i:take){
        if(vis[i.second])continue;
        int h=cmp(inp[i.second][0]>>cr,inp[i.second][1]>>cr);
        if(plane[h].size()==0)reset.push_back(h);
        plane[h].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++){
            for(int i:plane[cmp(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