Submission #253038

#	Time	Username	Problem	Language	Result	Execution time	Memory
253038		VEGAnn	Drzava (COCI15_drzava)	C++14	160 / 160	432 ms	8952 KiB

drzava

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define i2 array<int,2>
#define i3 array<int,3>
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
const int N = 50100;
const int md = 998244353;
const int PW = 233;
const ld E = 1e-9;
const int K = 33;
const int oo = 2e9;
vector<int> g[N];
set<i2> setik;
set<i2>::iterator iter;
int n, x[N], y[N], vl[N], k, k8, nm[N];
bool mrk[N], ff[K], f[K];

ll sqr(ll x) { return (x * x); }

ll dist(ll x1, ll y1, ll x2, ll y2){
    return sqr(x1 - x2) + sqr(y1 - y2);
}

bool cmp(int _x, int _y){
    return x[_x] < x[_y];
}

void dfs(int v){
    if (f[0]) return;

    mrk[v] = 1;

    fill(ff, ff + K, 0);

    ff[vl[v]] = 1;

    for (int i = 0; i < k; i++)
        if (f[i])
            ff[(i + vl[v]) % k] = 1;

    for (int i = 0; i < k; i++)
        f[i] |= ff[i];

    for (int u : g[v])
        if (!mrk[u])
            dfs(u);
}

bool ok(ll xx){
    for (int i = 0; i < n; i++) {
        g[i].clear();
        mrk[i] = 0;
    }

    setik.clear();

    int root = (int)(trunc(sqrt(xx)));

    for (int it = 0, ptr = 0; it < n; it++){
        int i = nm[it];

        while (ptr < it && sqr(x[i] - x[nm[ptr]]) > xx){
            setik.erase({y[nm[ptr]], nm[ptr]});
            ptr++;
        }

        int cnt = 1;

        for (iter = setik.lower_bound({y[i] - root, -oo}); iter != setik.end(); iter++, cnt++){
            i2 cur = (*iter);

            if (cur[0] > y[i] + root) break;

            if (cnt == k8)
                return 1;

            if (dist(x[i], y[i], x[cur[1]], cur[0]) <= xx){
                g[i].PB(cur[1]);
                g[cur[1]].PB(i);

                if (sz(g[i]) == k - 1)
                    return 1;
            }
        }

        setik.insert({y[i], i});
    }

    for (int i = 0; i < n; i++){
        if (mrk[i]) continue;

        fill(f, f + K, 0);

        dfs(i);

        if (f[0])
            return 1;
    }

    return 0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    k8 = (k << 3);

    for (int i = 0; i < n; i++){
        cin >> x[i] >> y[i] >> vl[i];
        vl[i] %= k;
        nm[i] = i;
    }

    sort(nm, nm + n, cmp);

    ll l = 1, r = ll(1e17);

    while (l < r){
        ll md = (l + r) >> 1;

        if (ok(md))
            r = md;
        else l = md + 1;
    }

    cout << fixed << setprecision(3) << sqrt(ld(l));

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8
• Subtask 13: 8 / 8
• Subtask 14: 8 / 8
• Subtask 15: 8 / 8
• Subtask 16: 8 / 8
• Subtask 17: 8 / 8
• Subtask 18: 8 / 8
• Subtask 19: 8 / 8
• Subtask 20: 8 / 8