Submission #692385

#	Time	Username	Problem	Language	Result	Execution time	Memory
692385		aidfnbvosdnvla	Circle selection (APIO18_circle_selection)	C++17	0 / 100	491 ms	32960 KiB

circle_selection

#define _USE_MATH_DEFINES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

constexpr int INF = 2e9;
constexpr int64_t INF_LL = 1e18 + 228;

typedef int64_t ll;
typedef long double ld;

bool STRS;

typedef array<int, 3> circ;

bool itr(circ l, circ r) {
    return (ll)(l[0] - r[0]) * (l[0] - r[0]) +
               (ll)(l[1] - r[1]) * (l[1] - r[1]) <=
           (ll)(l[2] + r[2]) * (l[2] + r[2]);
}

vector<int> solve1(int n, vector<circ> ar) {
    vector<int> ans(n, -1);
    for (int i = 0; i < n; ++i) {
        int it = (int)(max_element(ar.begin(), ar.end(),
                                   [](circ l, circ r) { return l[2] < r[2]; }) -
                       ar.begin());
        if (ar[it][2] == -1)
            break;
        for (int j = 0; j < n; ++j) {
            if (it != j && ar[j][2] != -1 && itr(ar[it], ar[j])) {
                ar[j][2] = -1;
                ans[j] = it;
            }
        }
        ans[it] = it;
        ar[it][2] = -1;
    }
    return ans;
}

vector<int> solve2(int n, vector<circ> ar) {
    vector<int> ans(n, -1);
    vector<int> ids(n);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int l, int r) {
        return pair<int, int>(ar[l][2], -l) > pair<int, int>(ar[r][2], -r);
    });
    set<pair<int, int>> ls;
    set<pair<int, int>> rs;
    for (int i = 0; i < n; ++i) {
        ls.insert({ar[i][0] - ar[i][2], i});
        rs.insert({ar[i][0] + ar[i][2], i});
    }
    for (auto &it : ids) {
        if (ans[it] != -1)
            continue;
        int lfs = ar[it][0] - ar[it][2];
        int rfs = ar[it][0] + ar[it][2];
        vector<int> del = {it};
        for (auto jt = ls.lower_bound({lfs, 0});
             jt != ls.end() && jt->first <= rfs; ++jt)
            del.push_back(jt->second);
        for (auto jt = rs.lower_bound({lfs, 0});
             jt != rs.end() && jt->first <= rfs; ++jt)
            del.push_back(jt->second);
        for (auto &jt : del) {
            ans[jt] = it;
            ls.erase({ar[jt][0] - ar[jt][2], jt});
            rs.erase({ar[jt][0] + ar[jt][2], jt});
        }
    }
    return ans;
}

vector<int> solve3(int n, vector<circ> ar) {
    vector<int> ans(n, -1);
    vector<circ> ev;
    ev.reserve(n * 2);
    for (int i = 0; i < n; ++i) {
        ev.push_back({ar[i][0] - ar[i][2], -1, i});
        ev.push_back({ar[i][0] + ar[i][2], 1, i});
    }
    sort(ev.begin(), ev.end());
    set<pair<int, int>> cur;
    vector<int> pr(n, -1);
    for (auto &it : ev) {
        if (it[1] == 1) {
            cur.erase({ar[it[2]][1], it[2]});
            continue;
        }
        auto tst = cur.insert({ar[it[2]][1], it[2]});
        //                assert(tst.second);
        auto jt = tst.first;
        if (jt != cur.begin()) {
            auto qt = prev(jt);
            if (itr(ar[qt->second], ar[jt->second])) {
                pr[qt->second] = jt->second;
                pr[jt->second] = qt->second;
//                int vl = qt->second;
//                cur.erase({ar[it[2]][1], it[2]});
//                cur.erase({ar[vl][1], vl});
//                continue;
            }
        }
        if (jt != prev(cur.end())) {
            auto qt = next(jt);
            if (itr(ar[qt->second], ar[jt->second])) {
                pr[qt->second] = jt->second;
                pr[jt->second] = qt->second;
//                int vl = qt->second;
//                cur.erase({ar[it[2]][1], it[2]});
//                cur.erase({ar[vl][1], vl});
//                continue;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        ans[i] = i;
        if (pr[i] != -1 && (ar[pr[i]][2] > ar[i][2] ||
                            (ar[pr[i]][2] == ar[i][2] && pr[i] < i)))
            ans[i] = pr[i];
    }
    return ans;
}

void solve(int TEST) {
    int n;
    cin >> n;
    vector<circ> ar(n);
    bool META_1_n_le_5000 = n <= 5000;
    bool META_2_y_eq_z = true;
    for (auto &it : ar) {
        for (auto &jt : it) {
            cin >> jt;
        }
        if (it[1] != 0)
            META_2_y_eq_z = false;
    }
    vector<int> ans;
    //    if (META_1_n_le_5000)
    //        ans = solve1(n, ar);
    //    else if (META_2_y_eq_z)
    //        ans = solve2(n, ar);
    //    else
    ans = solve3(n, ar);
    for (int i = 0; i < n; ++i)
        cout << ans[i] + 1 << " ";
    cout << "\n";
}

signed main() {
    (*cin.tie(0)).sync_with_stdio(0);
    STRS = false;
    int st = 0;
    while (STRS) {
        solve(st++);
        if (st % 100 == 0)
            cout << "NOTHING " << st << "\n";
    }
    int t = 1;
    //    cin >> t;
    for (int TEST = st; TEST < st + t; ++TEST)
        solve(TEST);
    return 0;
}

// 7
// 0 0 1
// 2 0 1
// 10 0 5
// 5 0 1
// 4 0 1
// 9 0 1
// 14 0 2

// 5
//-2 2 1
// 3 4 1
// 1 4 1
// 2 1 2
// 0 0 1

// 2
// 0 0 3
//-1 1 1

// 2
//-1 1 1
// 0 0 3

Compilation message (stderr)

circle_selection.cpp: In function 'void solve(int)':
circle_selection.cpp:157:10: warning: unused variable 'META_1_n_le_5000' [-Wunused-variable]
  157 |     bool META_1_n_le_5000 = n <= 5000;
      |          ^~~~~~~~~~~~~~~~
circle_selection.cpp:158:10: warning: variable 'META_2_y_eq_z' set but not used [-Wunused-but-set-variable]
  158 |     bool META_2_y_eq_z = true;
      |          ^~~~~~~~~~~~~

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