Submission #1109091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109091		lmToT27	Circle selection (APIO18_circle_selection)	C++17	19 / 100	539 ms	65720 KiB

circle_selection

        #include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()

typedef long long ll;

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 3e5 + 3;
const ll MOD[] = {1000000007, 998244353};

int n;
int ans[MAX];
ll x[MAX], y[MAX], r[MAX];

ll dist(int i, int j) {
        return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}

void bruteForce() {
        while (1) {
                int chosen = 0;
                for (int i = 1; i <= n; i++) if (!ans[i]) {
                        if (r[i] > r[chosen]) chosen = i;
                }
                if (!chosen) break;
                for (int i = 1; i <= n; i++) if (!ans[i]) {
                        if ((r[i] + r[chosen]) * (r[i] + r[chosen]) >= dist(i, chosen)) ans[i] = chosen; 
                }
        }
        for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}

template <typename dataType>
inline void compress(vector <dataType> &x) {
        sort(all(x));
        x.erase(unique(all(x)), x.end());
}

vector <int> f[2][MAX];
int st[2][MAX << 2];

bool cmp0(int i, int j) {
        return r[i] - x[i] < r[j] - x[j];
}

bool cmp1(int i, int j) {
        return r[i] + x[i] < r[j] + x[j];
}

int choose(int type, int i, int j) {
        if (i == 0) return j;
        if (j == 0) return i;
        if (type == 0) return r[i] - x[i] > r[j] - x[j] ? i : j;
        return r[i] + x[i] > r[j] + x[j] ? i : j;
}

void build(int id, int l, int r) {
        if (l == r) {
                for (int type = 0; type <= 1; type++) {
                        st[type][id] = f[type][l].empty() ? 0 : f[type][l].back();
                }
        } else {
                int mid = (l + r) / 2;
                build(id << 1, l, mid);
                build(id << 1 | 1, mid + 1, r);
                for (int type = 0; type <= 1; type++) st[type][id] = choose(type, st[type][id << 1], st[type][id << 1 | 1]);
        }
}

int get(int type, int u, int v, int id = 1, int l = 1, int r = n) {
        if (u > v || v < l || r < u) return 0;
        if (u <= l && r <= v) return st[type][id];
        int mid = (l + r) / 2;
        return choose(type, get(type, u, v, id << 1, l, mid), get(type, u, v, id << 1 | 1, mid + 1, r));
}

void del(int type, int pos, int id = 1, int l = 1, int r = n) {
        if (l == r) {
                f[type][l].pop_back();
                st[type][id] = f[type][l].empty() ? 0 : f[type][l].back();
        } else {
                int mid = (l + r) / 2;
                if (pos <= mid) del(type, pos, id << 1, l, mid);
                else del(type, pos, id << 1 | 1, mid + 1, r);
                st[type][id] = choose(type, st[type][id << 1], st[type][id << 1 | 1]);
        }
}

void Solve() {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];
        if (n <= 5000) return bruteForce();
        
        vector <ll> valX;
        for (int i = 1; i <= n; i++) valX.push_back(x[i]);
        compress(valX);

        for (int i = 1; i <= n; i++) {
                int id = lower_bound(all(valX), x[i]) - valX.begin() + 1;
                f[0][id].push_back(i);
                f[1][id].push_back(i);
        }

        for (int x = 1; x <= n; x++) {
                sort(all(f[0][x]), cmp0);
                sort(all(f[1][x]), cmp1);
        }

        build(1, 1, n);

        vector <int> idx(n);
        iota(all(idx), 1);
        sort(all(idx), [&](const int &i, const int &j) {
                if (r[i] != r[j]) return r[i] > r[j];
                return i < j;
        });

        for (int &i : idx) {
                if (ans[i]) continue;
                int id = lower_bound(all(valX), x[i]) - valX.begin() + 1;

                while (1) {
                        int chosen = get(1, 1, id);
                        if (x[i] - x[chosen] > r[i] + r[chosen]) break;
                        if (!ans[chosen]) ans[chosen] = i; 
                        if (chosen) {
                                int pos = lower_bound(all(valX), x[chosen]) - valX.begin() + 1;
                                del(1, pos);
                        }
                        else break;
                }

                while (1) {
                        int chosen = get(0, id, n);
                        if (x[chosen] - x[i] > r[i] + r[chosen]) break;
                        if (!ans[chosen]) ans[chosen] = i; 
                        if (chosen) {
                                int pos = lower_bound(all(valX), x[chosen]) - valX.begin() + 1;
                                del(0, pos);
                        }
                        else break;
                }
        }

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

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

        #define TASK "CC"
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }
        
        if (fopen("TASK.INP", "r")) {
                freopen("TASK.INP", "r", stdin);
                freopen("TASK.OUT", "w", stdout);
        }
        
        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int32_t main()':
circle_selection.cpp:168:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:169:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:173:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:174:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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