oj.uz

Submission #89553

# Submission time Handle Problem Language Result Execution time Memory
89553 2018-12-15T16:42:58 Z jasony123123 Drzava (COCI15_drzava) C++11
160 / 160
 488 ms 15308 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
typedef pair<char, char> pcc;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
inline void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */
#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/**********************COCI 16-17 R2 P6*****************************/

#define X first.first
#define Y first.second
const int MAXN = 50000; 
const int MAXK = 30;
int N, K;
pair<pii, int> points[MAXN];

v<int> adj[MAXN];
bool vis[MAXN];


bool canZero(v<int> &kvals) {
	// [kvals.size()+1][K]
	v<v<int>> dp(kvals.size() + 1, v<int>(K, 0));
	dp[0][0] = 1;
	FOR(i, 0, kvals.size()) {
		FOR(k, 0, K) {
			minn(dp[i + 1][k] += dp[i][k], 4);
			minn(dp[i + 1][(k + kvals[i]) % K] += dp[i][k], 4);
		}
	}
	return dp[kvals.size()][0] > 1;
}

void dfs(int x, v<int> &ks) {
	if (vis[x]) return;
	vis[x] = 1;
	ks.push_back(points[x].second);
	for (int c : adj[x])
		dfs(c, ks);
}

bool checkGraph() {
	fill(vis, vis + N, 0);
	FOR(i, 0, N) {
		if (!vis[i]) {
			v<int> kvals;
			dfs(i, kvals);
			if (kvals.size() >= K || canZero(kvals))
				return 1;
		}
	}
	return 0;
}

inline double dist(pii a, pii b) {
	ll sq = (ll)(a.first - b.first)*(a.first - b.first) + (ll)(a.second - b.second)*(a.second - b.second);
	return sqrt(sq);
}
inline pii rev(pii a) {
	return{ a.second, a.first };
}
bool test(ll sqD) {
	double d = (double)sqrt(sqD) + 1e-6;
	set<pair<pii, int>> active; // < <y, x>, idx >

	for (int i = 0, j = 0; i < N; i++) {
		adj[i].clear();

		while (j < i && points[i].X - points[j].X > d) {
			active.erase({ rev(points[j].first), j });
			j++;
		}

		if (active.size()) {
			for (auto it = active.lower_bound({ {points[i].Y - d, -1}, -1 });
				it != active.end() && it->first.first <= points[i].Y + d;
				it++)
			{
				double tempd = dist(it->first, rev(points[i].first));
				if (tempd <= d) {
					adj[i].push_back(it->second);
					adj[it->second].push_back(i);
				}
				if (adj[i].size() >= K)
					return 1;
			}
		}
		active.insert({ rev(points[i].first), i });
	}

	return checkGraph();
}


void init() {
	cin >> N >> K;
	FOR(i, 0, N) {
		cin >> points[i].first.first >> points[i].first.second >> points[i].second;
		points[i].second %= K;
	}
	sort(points, points + N);
}

int main() {
	io();
	init();
	// sq dist
	ll lo = 0, hi = (ll)(2e16 + 10LL);
	while (lo<hi) {
		ll mid = (hi + lo) / 2;
		if (test(mid) == false)
			lo = mid + 1;
		else
			hi = mid;
	}
/*	FOR(x,0,100)
		cout << "test " << x << ": " << test(x) << "\n";
	test(4);
	cout << lo << "\n";*/
	cout << fixed << setprecision(3) << sqrt(lo) << "\n";
	return 0;
}

Compilation message

drzava.cpp: In function 'bool checkGraph()':
drzava.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (kvals.size() >= K || canZero(kvals))
        ~~~~~~~~~~~~~^~~~
drzava.cpp: In function 'bool test(ll)':
drzava.cpp:113:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (adj[i].size() >= K)
         ~~~~~~~~~~~~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1500 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
8.0 / 8.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1904 KB Output is correct
2 Correct 6 ms 1904 KB Output is correct

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1924 KB Output is correct
2 Correct 9 ms 1924 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1924 KB Output is correct
2 Correct 95 ms 3136 KB Output is correct

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11244 KB Output is correct
2 Correct 488 ms 12028 KB Output is correct

Subtask #12
8.0 / 8.0

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

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12028 KB Output is correct
2 Correct 394 ms 12028 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12028 KB Output is correct
2 Correct 355 ms 12768 KB Output is correct

Subtask #15
8.0 / 8.0

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

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12768 KB Output is correct
2 Correct 291 ms 12768 KB Output is correct

Subtask #17
8.0 / 8.0

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

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 257 ms 15308 KB Output is correct

Subtask #19
8.0 / 8.0

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

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15308 KB Output is correct
2 Correct 267 ms 15308 KB Output is correct