oj.uz

Submission #974820

# Submission time Handle Problem Language Result Execution time Memory
974820 2024-05-03T20:21:40 Z efedmrlr Circle selection (APIO18_circle_selection) C++17
35 / 100
 1093 ms 112368 KB 
#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(S.size() == 0) return;
    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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Runtime error 2 ms 2908 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 41664 KB Output is correct
2 Correct 562 ms 42068 KB Output is correct
3 Correct 600 ms 42248 KB Output is correct
4 Correct 560 ms 41392 KB Output is correct
5 Correct 636 ms 40624 KB Output is correct
6 Correct 773 ms 49692 KB Output is correct
7 Correct 671 ms 43140 KB Output is correct
8 Correct 670 ms 43976 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 196 ms 14444 KB Output is correct
3 Correct 868 ms 49076 KB Output is correct
4 Correct 975 ms 48568 KB Output is correct
5 Correct 1093 ms 47608 KB Output is correct
6 Correct 366 ms 25532 KB Output is correct
7 Runtime error 153 ms 20016 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 46856 KB Output is correct
2 Correct 522 ms 112368 KB Output is correct
3 Correct 546 ms 40964 KB Output is correct
4 Correct 510 ms 90508 KB Output is correct
5 Correct 484 ms 102020 KB Output is correct
6 Correct 547 ms 41688 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Runtime error 2 ms 2908 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Runtime error 2 ms 2908 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -