oj.uz

Submission #875379

# Submission time Handle Problem Language Result Execution time Memory
875379 2023-11-19T12:14:38 Z serifefedartar Drzava (COCI15_drzava) C++17
64 / 160
 236 ms 8912 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20; 
const ll MAXN = 5e4 + 101;

struct P {
	double x, y;
	ll k;
	void read() {
		cin >> x >> y >> k;
	}
	P() { }
	P(double _x, double _y, ll _k) : x(_x), y(_y), k(_k) { }
};

vector<P> v;
set<pair<double,int>> s;
int par[MAXN], sz[MAXN], N, K;
int find(int node) {
	if (node == par[node])
		return node;
	return par[node] = find(par[node]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return ; 
	if (sz[b] > sz[a])
		swap(a, b);
	par[b] = a;
	sz[a] += sz[b];
}

int dp[MAXN][31];
ll dist(int a, int b) {
	ll dx = v[a].x - v[b].x;
	ll dy = v[a].y - v[b].y;
	return dx * dx + dy * dy;
}

bool check(double d) {
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < MAXN; i++)
		par[i] = i, sz[i] = 1;

	int l = 0, r = 0;
	for (r = 0; r < N; r++) {
		int R = r;
		while (l < N && v[r].x - v[l].x > d) {
			s.erase({v[l].y, l});
			l++;
		}
		while (R < N && v[r].x == v[R].x) {
			s.insert({v[R].y, R});
			if (s.size() >= 8 * K)
				return true;

			auto it = s.lower_bound({v[R].y - d, -1});
			for ( ; it != s.end() && (*it).f <= v[r].y + d; it++) {
				if (dist(R, (*it).s) <= d * d)
					unite(R, (*it).s);
				if (sz[find(R)] >= K)
					return true;
			}
			R++;
		}
		r = R - 1;
	}

	for (int i = 0; i < N; i++) {
		int p = find(i);
		int new_dp[31];
		for (int j = 0; j < 31; j++)
			new_dp[j] = dp[p][j];
		for (int j = K-1; j >= 0; j--) {
			if (dp[p][j])
				new_dp[(j + v[i].k) % K] = true;
		}
		for (int j = 0; j < 31; j++)
			dp[p][j] = new_dp[j];
		dp[p][v[i].k] = true;
	}

	for (int i = 0; i < N; i++) {
		if (dp[find(i)][0])
			return true;
	}
	return false;
}

int main() {
	fast
	cin >> N >> K;

	v = vector<P>(N);
	for (int i = 0; i < N; i++) {
		v[i].read();
		v[i].k %= K;
	}
	sort(v.begin(), v.end(), [&](P A, P B) {
		return make_pair(A.x, A.y) < make_pair(B.x, B.y);
	});

	double L = 0.0, R = 200000000.0;
	double ans = -1.0;
	while (R - L > 0.000001) {
		double mid = L + (R-L) / 2;
		if (check(mid)) {
			R = mid;
			ans = mid;
		} else
			L = mid;
	}
	cout << setprecision(3) << fixed << ans << "\n";
}

Compilation message

drzava.cpp: In function 'bool check(double)':
drzava.cpp:63:17: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<double, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |    if (s.size() >= 8 * K)
      |                 ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6748 KB Output is correct
2 Correct 8 ms 6936 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Correct 7 ms 6928 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6744 KB Output is correct
2 Correct 12 ms 6748 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Correct 11 ms 6748 KB Output is correct

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Incorrect 10 ms 6748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6928 KB Output is correct
2 Correct 11 ms 6964 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Correct 12 ms 6980 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Correct 10 ms 6748 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6748 KB Output is correct
2 Incorrect 18 ms 7464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Incorrect 30 ms 8020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6744 KB Output is correct
2 Incorrect 29 ms 7896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6748 KB Output is correct
2 Incorrect 28 ms 7988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Incorrect 35 ms 8064 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6744 KB Output is correct
2 Incorrect 30 ms 8048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Correct 236 ms 8912 KB Output is correct

Subtask #16
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6744 KB Output is correct
2 Incorrect 30 ms 8788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6748 KB Output is correct
2 Incorrect 37 ms 8868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #18
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6920 KB Output is correct
2 Incorrect 30 ms 8032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6748 KB Output is correct
2 Incorrect 30 ms 8788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #20
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6744 KB Output is correct
2 Incorrect 30 ms 8788 KB Output isn't correct
3 Halted 0 ms 0 KB -