제출 #974806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
974806		efedmrlr	원 고르기 (APIO18_circle_selection)	C++17	35 / 100	764 ms	119872 KiB

circle_selection

#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 3e5 + 5;
const int INF = 1e9 + 500;
const int SHIFT = 1e9 + 2;
vector<array<int, 3> > p;
vector<set<array<int, 2> > > st;
vector<int> xc;
int rc = 0;
set<pair<int, int> > S;
lli sqr(int x) {
    return 1ll * x * x;
}

bool query(int x, int y) {
    return sqr(p[x][1] - p[y][1]) + sqr(p[x][2] - p[y][2]) <= sqr(p[x][0] + p[y][0]);
}

void printp(int ind) {
    cout << "ind: " << ind + 1 << " rad:" << p[ind][0] << " x:" << p[ind][1] << " y:" << p[ind][2] << "\n";
}

void rescale(int r) {
    rc = r;
    st.clear();
    xc.clear();
    for(auto z : S) {
        int j = z.second;
        auto &c = p[j]; 
        for(int i = -2; i <= 2; i++) {
            xc.pb(c[1] / r + i);
        }
    }
    sort(all(xc));
    xc.resize(unique(all(xc)) - xc.begin());
    st.assign(xc.size(), set<array<int, 2> >());
    for(auto z : S) {
        int i = z.second;
        auto &c = p[i];
        int xx = lower_bound(all(xc), c[1] / r) - xc.begin();
        st[xx].insert({c[2] / r, i});
    }
    
    // for(int i = 0; i < xc.size(); i++) {
    //     cout << "i:" << i << " row:" << xc[i] << "\n";
    //     for(auto c : st[i]) {
    //         cout << "c0:" << c[0] << " c1:" << c[1] << "|| "; 
    //     }
    //     cout << "\n";
    // }
}

int n;
vector<int> ans(N, 0);
void eliminate() {
    int ind = (*S.begin()).second;
    ans[ind] = ind;
    S.erase(S.begin());
    if(p[ind][0] * 2 < rc) {
        rescale(p[ind][0]);
    }
    int xx = lower_bound(all(xc), p[ind][1] / rc) - xc.begin();
    int yy = p[ind][2] / rc;
    st[xx].erase({yy, ind});
    // printp(ind);
    // cout << "xx:" << xx << " yy:" << yy << "\n";
    // cout << "eliminates: ";
    for(int i = xx - 2; i <= xx + 2; i++) {
        for(auto j = st[i].lower_bound({yy - 2, 0}); j != st[i].end() && (*j)[0] <= yy + 2; ) {
            // printp((*j)[1]);
            if(query((*j)[1], ind)) {
                // cout << "killed\n";
                ans[(*j)[1]] = ind;
                S.erase({-p[(*j)[1]][0], (*j)[1]});
                j = st[i].erase(j);
            }
            else {
                j++;
            }
        }
    } 
    // cout << "\n\n";
}

void solve() {
    cin >> n;
    p.resize(n);
    REP(i, n) {

        cin >> p[i][1] >> p[i][2] >> p[i][0];
        // p[i][1] += SHIFT;
        // p[i][2] += SHIFT;
        S.insert({-p[i][0], i});
    }
    // cout << "zort" << endl;
    rescale(-(*S.begin()).first);
    // cout << "zort2" << endl;
    while(S.size()) {
        eliminate();
    }
    REP(i, n) {
        cout << ans[i] + 1 << " ";
    }
    cout << "\n";

}


signed main() {
    fastio();
    solve();
}

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