oj.uz

Submission #252790

# Submission time Handle Problem Language Result Execution time Memory
252790 2020-07-26T09:30:03 Z islingr Drzava (COCI15_drzava) C++14
160 / 160
 302 ms 5232 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(e, x) for (auto &e : x)
#define eb(x...) emplace_back(x)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
#define lb(x...) lower_bound(x)
#define f first
#define s second

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 1 << 16, K = 1 << 6;
const ll inf = 2e8;

short k;

int n, cur;
vector<int> cmp[N];
bool dp[K][K];
int nxt[N], rnk[N];

int head(int u) { return nxt[u] < 0 ? u : nxt[u] = head(nxt[u]); }
void unite(int u, int v) {
	u = head(u); v = head(v);
	if (u == v) return;
	if (rnk[u] > rnk[v]) nxt[v] = u;
	else {
		nxt[u] = v;
		if (rnk[u] == rnk[v]) ++rnk[v];
	}
}

using pii = pair<int, int>;

pair<pii, short> tmp[N];
pii p(int i) { return tmp[i].f; }
short v(int i) { return tmp[i].s; }

ll norm(const pii &p, const pii &q) {
	return 1ll * (p.f - q.f) * (p.f - q.f) + 1ll * (p.s - q.s) * (p.s - q.s);
}

bool f(ll d) {
	int r = floor(sqrt(ld(d)));

	set<pair<int, int>> S;

	int l = 0;
	rep(u, 0, n) nxt[u] = rnk[u] = -1, cmp[u].clear();
	rep(i, 0, n) {
		while (p(i).f - p(l).f > r) S.erase({p(l).s, l}), ++l;
		int cnt = 0;
		for (auto it = S.lb({p(i).s - r, 0});
			it != end(S) && it->f - r <= p(i).s; ++it) {
			if (norm(p(it->s), p(i)) <= d) {
				unite(it->s, i);
				if (++cnt > k) return true;
			}
		}
		S.insert({p(i).s, i});
	}

	rep(u, 0, n) cmp[head(u)].eb(u);

	rep(z, 0, n) {
		auto &a = cmp[z]; int n = sz(a);
		if (a.empty()) continue;
		if (sz(a) > k) return true;
		rep(i, 0, n) rep(w, 0, k) dp[i][w] = 0;
		dp[0][v(a[0])] = 1;
		rep(i, 1, n) {
			dp[i][v(a[i])] = 1;
			rep(w, 0, k)
				if (dp[i - 1][w])
					dp[i][(w + v(a[i])) % k] = dp[i][w] = true;
			if (dp[i][0]) return true;
		}
	}
	return false;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> k;
	rep(i, 0, n) {
		int x, y, c; cin >> x >> y >> c;
		tmp[i] = {{x, y}, c % k};
	}
	sort(tmp, tmp + n);
	
	ll l = 0, r = inf * inf;
	while (r - l > 1) {
		ll m = l + (r - l + 1) / 2;
		if (f(m)) r = m;
		else l = m; 
	}

	cout << fixed << setprecision(3) << sqrt(ld(r));
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 5 ms 1920 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 5 ms 1920 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 4 ms 1920 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 5 ms 1920 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 5 ms 1920 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 4 ms 1920 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 82 ms 3064 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 297 ms 5168 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 302 ms 5036 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 264 ms 4856 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 269 ms 4984 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 293 ms 5232 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 194 ms 4472 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1920 KB Output is correct
2 Correct 220 ms 4604 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 206 ms 4860 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 198 ms 4856 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 222 ms 4732 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 198 ms 4600 KB Output is correct