제출 #710149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710149		vjudge1	원 고르기 (APIO18_circle_selection)	C++17	0 / 100	2553 ms	54388 KiB

circle_selection

/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc
*/

#include <bits/stdc++.h>
#define endl '\n'

#define int long long

using namespace std;

const int N = 3e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

array<int, 3> b[N];
set <array<int, 3>> s;
int ans[N];
bool f[N];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int randint(int l, int r){
    return uniform_int_distribution <int> (l, r) (rng);
}

double randdouble(double l, double r){
    return uniform_real_distribution <double> (l, r) (rng);
}

struct point{
    int x, y;
 
    bool operator <(const point& p) const{
        return x < p.x || (x == p.x && y < p.y);
    }
    
    bool operator >(const point& p) const{
        return x > p.x || (x == p.x && y > p.y);
    }
} a[N];
 
pair<long double, int> d[N];
 
inline int dist(point a, point b){
    int h1 = a.x - b.x;
    int h2 = a.y - b.y;
 
    return h1 * h1 + h2 * h2;
}
 
inline long double sdist(point a, point b){
    return sqrt(dist(a, b));
}

bool isintersect(array<int, 3> a, array<int, 3> b){
    point a1, b1;
    a1.x = a[0]; a1.y = a[1];
    b1.x = b[0]; b1.y = b[1];
    return dist(a1, b1) <= (a[2] + b[2]) * (a[2] + b[2]);
}

void tryshit(){
    array<int, 3> last = {-INF, -INF, -INF};
    int sz = s.size();
    for(int i = 1; i <= sz; ++i){
        auto it = s.upper_bound(last);
        if (it == s.end()) break;
        array<int, 3> state = *it;
        int id = state[2];

        last = state;

        int ct = 0;
        auto it2 = it;
        while(1){
            ++it2; ++ct;
            if (it2 == s.end()) break;
            int i = (*it2)[2];
            if (!ans[i]){
                if (isintersect(b[i], b[id])){
                    s.erase(state);
                    ans[i] = id; ans[id] = id;
                    s.erase({-b[i][2], b[i][2], i});
                    break;
                }
            }
            if (ct == 20) break;
        }

        auto it3 = s.end();
        ct = 0;
        while(1){
            --it3; ++ct;
            if (it3 == it) break;
            int i = (*it3)[2];
            if (!ans[i]){
                if (isintersect(b[i], b[id])){
                    s.erase(state);
                    ans[i] = id; ans[id] = id;
                    s.erase({-b[i][2], b[i][2], i});
                    break;
                }
            }
            if (ct == 20) break;
        }
    }
}

inline int cmp(int idi, int idj){
    if (b[idi][2] > b[idj][2] || (b[idi][2] == b[idj][2] && idi < idj)){
        return idi;
    } else {
        return idj;
    }
}

void tryshit2(){
    if (s.empty()) return;
    vector <array<int, 3>> v;
    for(array<int, 3> st: s){
        v.push_back(st);
    }

    vector <int> er;

    for(array<int, 3> st: v){
        int i = st[2];
        for(int tr = 1; tr <= 50; ++tr){
            int r = randint(0, (int)v.size() - 1);
            int j = v[r][2];

            if (i != j && isintersect(b[i], b[j])){
                ans[i] = ans[j] = cmp(i, j);
                er.push_back(i); er.push_back(j);
            }
        }
    }

    for(int p: er){
        s.erase({b[p][2], p});
    }

    v.clear();
}

void tryshit3(){
    if (s.empty()) return;
    vector <array<int, 3>> v;
    for(array<int, 3> st: s){
        v.push_back(st);
    }

    vector <int> er;

    for(int i1 = 0; i1 < (int)v.size(); ++i1){
        int i = v[i1][2];
        for(int i2 = 0; i2 < i1; ++i2){
            int j = v[i2][2];

            if (i != j && isintersect(b[i], b[j])){
                ans[i] = ans[j] = cmp(i, j);
                er.push_back(i); er.push_back(j);
            }
        }
    }
}
 
void solve(){
    int n; cin >> n;
    for(int i = 1; i <= n; ++i){
        int x, y, r; cin >> x >> y >> r;
        b[i] = {x, y, r};
        a[i] = {x, y};
    }
    
    point p1 = a[1], p2 = a[1];
    point p3 = {a[1].y, a[1].x}, p4 = {a[1].y, a[1].x};
 
    for(int i = 1; i <= n; ++i){
        p1 = min(p1, a[i]);
        p2 = max(p2, a[i]);
        p3 = min(p3, {a[1].y, a[1].x});
        p4 = max(p4, {a[1].y, a[1].x});
 
        d[i].second = i;
    }
    for(int i = 1; i <= n; ++i){
        d[i].first = sdist(a[i], p1) + 10 * sdist(a[i], p2) + 100 * sdist(a[i], p3) + 1000 * sdist(a[i], p4);
    }
    sort(d + 1, d + n + 1);
 
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= min(n, i + 100); ++j){
            int idi = d[i].second, idj = d[j].second;
            if (isintersect(b[idi], b[idj])){
                ans[idi] = ans[idj] = cmp(idi, idj);
            }
        }
    }

    for(int i = 1; i <= n; ++i){
        if (!ans[i]) s.insert({-b[i][2], b[i][2], i});
    }

    for(int i = 1; i <= 5; ++i){
        tryshit();
    }
    tryshit2();

    if (s.size() <= 10000){
        tryshit3();
    }

    for(int i = 1; i <= n; ++i){
        if (!ans[i]) ans[i] = i;
    }

    for(int i = 1; i <= n; ++i) cout << ans[i] << " "; 
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("codeforces.inp","r",stdin);
    // freopen("codeforces.out","w",stdout);

    int t = 1; // cin >> t;
    while (t--)
    {
        solve();
    }
}

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