oj.uz

Submission #252758

# Submission time Handle Problem Language Result Execution time Memory
252758 2020-07-26T08:27:32 Z islingr Drzava (COCI15_drzava) C++14
56 / 160
 1000 ms 4984 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 ld eps = 1e-4;
const int N = 1 << 16, K = 1 << 6;
const ll inf = 2e8;
using point = complex<ll>;

point p[N];
short v[N], k;

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

int head(int u) { return nxt[u] != u ? nxt[u] = head(nxt[u]) : u; }
void unite(int u, int v) { nxt[head(u)] = head(v); }

bool f(ld r) {
	set<pair<ll, int>> S;
	int l = 0;
	rep(u, 0, n) nxt[u] = u;
	rep(i, 0, n) {
		if (real(p[i]) - real(p[l]) > r)
			S.erase({imag(p[l]), l}), ++l;
		for (auto it = S.lb({ceil(imag(p[i]) - r), -inf});
			it != end(S) && it->f - r <= imag(p[i]); ++it)
			if (norm(p[it->s] - p[i]) <= r * r)
				unite(it->s, i);
		S.insert({imag(p[i]), i});
	}
	rep(u, 0, n) cmp[u].clear();
	rep(u, 0, n) cmp[head(u)].eb(u);
	rep(z, 0, n) {
		auto &a = cmp[z];
		if (a.empty()) continue;
		if (sz(a) > k) return true;
		int n = sz(a);
		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[n - 1][0]) return true;
	}
	return false;
}

pair<point, short> tmp[N];

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, [&](auto a, auto b) {
		if (real(a.f) == real(b.f)) return imag(a.f) < imag(b.f);
		return real(a.f) < real(b.f);
	});
	rep(i, 0, n) tie(p[i], v[i]) = tmp[i];

	ld l = 0, r = inf;
	while (r - l > eps) {
		ld m = l + (r - l) / 2;
		if (f(m)) r = m;
		else l = m; 
	}
	cout << fixed << setprecision(3) << 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 203 ms 2056 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 161 ms 2056 KB Output is correct

Subtask #5
8.0 / 8.0

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

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Execution timed out 1085 ms 3520 KB Time limit exceeded

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Execution timed out 1085 ms 4624 KB Time limit exceeded

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Execution timed out 1077 ms 4724 KB Time limit exceeded

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Execution timed out 1091 ms 4600 KB Time limit exceeded

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Execution timed out 1093 ms 4728 KB Time limit exceeded

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Execution timed out 1091 ms 4712 KB Time limit exceeded

Subtask #15
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Execution timed out 1085 ms 4856 KB Time limit exceeded

Subtask #16
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Execution timed out 1094 ms 4984 KB Time limit exceeded

Subtask #17
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Execution timed out 1085 ms 4804 KB Time limit exceeded

Subtask #18
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Execution timed out 1091 ms 4932 KB Time limit exceeded

Subtask #19
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Execution timed out 1083 ms 4900 KB Time limit exceeded

Subtask #20
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Execution timed out 1094 ms 4728 KB Time limit exceeded