Submission #232578

#	Time	Username	Problem	Language	Result	Execution time	Memory
232578		alishahali1382	Drzava (COCI15_drzava)	C++14	160 / 160	227 ms	1404 KiB

drzava

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define get(x, y) (((x)>>(y))&1)

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=50010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans;
piii A[MAXN];
int par[MAXN], dp[MAXN];
set<pii> st;

int getpar(int x){
	if (par[x]==x) return x;
	return par[x]=getpar(par[x]);
}
bool join(int x, int y){
	x=getpar(x);
	y=getpar(y);
	if (x==y) return 0;
	par[y]=x;
	//debug2(x, y)
	//cerr<<dp[x]<<' '<<dp[y]<<" : ";
	for (int i=1; i<k; i++) if (get(dp[x], i) && get(dp[y], k-i)) return 1;
	int tmp=dp[x];
	for (int i=1; i<k; i++) if (get(dp[y], i)){
		dp[x]|=((((1<<(k-i))-1)&tmp)<<i);
		dp[x]|=(tmp>>(k-i));
	}
	//cerr<<dp[x]<<endl;
	return 0;
}

ld dist(int i, int j){
	ld dx=A[i].first.first-A[j].first.first, dy=A[i].first.second-A[j].first.second;
	return sqrt(dx*dx+dy*dy);
}

bool check(ld D){
	if (D<1) return 0;
	int DD=D+1;
	iota(par, par+MAXN, 0);
	for (int i=1; i<=n; i++) dp[i]=(1|(1<<A[i].second));
	st.clear();
	int j=1;
	for (int i=1; i<=n; i++){
		while (A[i].first.first-A[j].first.first>DD){
			st.erase({A[j].first.second, j});
			j++;
		}
		//debug2(i, j)
		int y=A[i].first.second;
		auto it=st.lower_bound({y-DD, 0});
		while (1){
			if (it==st.end() || (it->first)>y+DD) break ;
			if (dist(i, (it->second))<=D){
				if (join(i, (it->second))) return 1;
			}
			it=st.upper_bound(*it);
		}
		st.insert({y, i});
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>k;
	for (int i=1; i<=n; i++) cin>>A[i].first.first>>A[i].first.second>>A[i].second, A[i].second%=k;
	sort(A+1, A+n+1);
	/*
	debug(check(20000))
	return 0;
	*/
	ld dwn=0, up=2e8;
	for (int i=0; i<50; i++){
		ld mid=(dwn+up)/2;
		if (check(mid)) up=mid;
		else dwn=mid;
	}
	cout<<setprecision(3)<<fixed<<up<<'\n';
	
	return 0;
}
/*
6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10


5 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1

*/

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8
• Subtask 13: 8 / 8
• Subtask 14: 8 / 8
• Subtask 15: 8 / 8
• Subtask 16: 8 / 8
• Subtask 17: 8 / 8
• Subtask 18: 8 / 8
• Subtask 19: 8 / 8
• Subtask 20: 8 / 8