oj.uz

Submission #710088

# Submission time Handle Problem Language Result Execution time Memory
710088 2023-03-15T04:32:48 Z vjudge1 Circle selection (APIO18_circle_selection) C++17
0 / 100
 3000 ms 40668 KB 
/*
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];

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 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])){
                if (b[idi][2] > b[idj][2] || (b[idi][2] == b[idj][2] && idi < idj)){
                    ans[idi] = ans[idj] = idi;
                } else {
                    ans[idi] = ans[idj] = idj;
                }
            }
        }
    }

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

    //assert(s.size() <= 100);

    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;
        }
    }

    while (!s.empty()){
        array<int, 3> state = *s.begin();
        int id = state[2];

        s.erase(state);

        ans[id] = id;

        int ct = 0;
        for(array<int, 3> st2 : s){
            int i = st2[2];
            if (!ans[i]){
                if (isintersect(b[i], b[id])){
                    ans[i] = id;
                    s.erase({-b[i][2], b[i][2], i});
                    break;
                }
            }
            if (ct == 20) break;
        }
    }

    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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 407 ms 25724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 3068 ms 14460 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 40668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -