Submission #395775

#TimeUsernameProblemLanguageResultExecution timeMemory
395775rainboyDrzava (COCI15_drzava)C++98
160 / 160
714 ms3488 KiB
#include <math.h> #include <stdio.h> #include <string.h> #define N 50000 #define K 30 unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } int xx[N], yy[N], aa[N], ii[N], n, k; void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) if (xx[ii[j]] == xx[i_]) j++; else if (xx[ii[j]] < xx[i_]) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } sort(ii, l, i); l = k; } } int zz[1 + N], ll[1 + N], rr[1 + N], ii_[1 + N], _, u_, l_, r_; int node(int i) { zz[_] = rand_(), ll[_] = rr[_] = 0; ii_[_] = i; return _++; } void split(int u, int y, int i) { int c; if (u == 0) { u_ = l_ = r_ = 0; return; } c = yy[ii_[u]] != y ? yy[ii_[u]] - y : ii_[u] - i; if (c < 0) { split(rr[u], y, i); rr[u] = l_, l_ = u; } else if (c > 0) { split(ll[u], y, i); ll[u] = r_, r_ = u; } else { u_ = u, l_ = ll[u], r_ = rr[u]; ll[u] = rr[u] = 0; } } int merge(int u, int v) { if (u == 0) return v; if (v == 0) return u; if (zz[u] < zz[v]) { rr[u] = merge(rr[u], v); return u; } else { ll[v] = merge(u, ll[v]); return v; } } void tr_add(int i) { split(u_, yy[i], i); u_ = merge(merge(l_, node(i)), r_); } void tr_remove(int i) { split(u_, yy[i], i); u_ = merge(l_, r_); } int ds[N]; int find(int i) { return ds[i] < 0 ? i : (ds[i] = find(ds[i])); } void join(int i, int j) { i = find(i); j = find(j); if (i == j) return; if (ds[i] > ds[j]) ds[i] = j; else { if (ds[i] == ds[j]) ds[i]--; ds[j] = i; } } long long d2; int ok(int i, int j) { return (long long) (xx[j] - xx[i]) * (xx[j] - xx[i]) + (long long) (yy[j] - yy[i]) * (yy[j] - yy[i]) <= d2; } int k_; int join1(int i, int u) { if (u != 0) { if (ok(ii_[u], i)) { join(ii_[u], i); if (--k_ == 0) return 1; } if (join1(i, ll[u])) return 1; if (join1(i, rr[u])) return 1; } return 0; } int join_(int i, int yl, int yr) { int l; split(u_, yl, -1), l = l_; split(r_, yr + 1, -1); k_ = k; if (join1(i, l_)) return 1; u_ = merge(merge(l, l_), r_); return 0; } int dp_add(char *dp, int a) { static char dq[K]; int s; memset(dq, 0, k * sizeof *dq); dq[a % k] = 1; for (s = 0; s < k; s++) if (dp[s]) dq[s] = dq[(s + a) % k] = 1; memcpy(dp, dq, k * sizeof *dq); return dp[0]; } int solve() { static char dp[N][K]; int d, i, j; _ = 1; memset(ds, -1, n * sizeof *ds); d = sqrt(d2); for (i = 0, j = 0; j < n; j++) { int i_ = ii[j], yl, yr; while ((long long) (xx[i_] - xx[ii[i]]) * (xx[i_] - xx[ii[i]]) > d2) tr_remove(ii[i++]); yl = yy[i_] - d, yr = yy[i_] + d; while ((long long) (yy[i_] - yl) * (yy[i_] - yl) > d2) yl++; while ((long long) (yy[i_] - yl + 1) * (yy[i_] - yl + 1) <= d2) yl--; while ((long long) (yy[i_] - yr) * (yy[i_] - yr) > d2) yr--; while ((long long) (yy[i_] - yr + 1) * (yy[i_] - yr + 1) <= d2) yr++; if (join_(i_, yl, yr)) return 1; tr_add(i_); } for (i = 0; i < n; i++) if (ds[i] < 0) memset(dp[i], 0, k * sizeof *dp[i]); for (i = 0; i < n; i++) if (dp_add(dp[find(i)], aa[i])) return 1; return 0; } int main() { int i; long long lower, upper; scanf("%d%d", &n, &k); for (i = 0; i < n; i++) scanf("%d%d%d", &xx[i], &yy[i], &aa[i]); for (i = 0; i < n; i++) ii[i] = i; sort(ii, 0, n); lower = 0, upper = 20000000000000000; while (upper - lower > 1) { d2 = (lower + upper) / 2; if (solve()) upper = d2; else lower = d2; } printf("%.3f\n", sqrt(upper)); return 0; }

Compilation message (stderr)

drzava.cpp: In function 'int main()':
drzava.cpp:193:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  193 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
drzava.cpp:195:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  195 |   scanf("%d%d%d", &xx[i], &yy[i], &aa[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...