Submission #1255679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255679		settop	Mobile (BOI12_mobile)	C++20	100 / 100	508 ms	71192 KiB

mobile

#include<bits/stdc++.h>
 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define double long double
#define int long long 
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define eb emplace_back
#define S second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
#define sz(x) (int)x.size()
const int MAXN=1e6+10;
const int MAXL=5e2+10;
const int inf=1e17;
const int MOD=1e9+7;
 
typedef pair<double,double> pii;
typedef tuple<int,int,int> trio;
typedef tuple<int,int,int,int> squad;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,k;
double l[MAXN],r[MAXN];
vector<pii> v;

double sq(double x){
	return x*x;
}

int32_t main(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("cowrun.in","r",stdin);
	//freopen("cowrun.out","w",stdout);

	cin>>n>>k;
	v.resize(n);
	for(auto &[u,j]:v) cin>>u>>j;

	l[0]=0,r[0]=k;
	stack<int> st;
	st.push(0);
	fall(i,1,n-1){	
		while(!st.empty()){
			auto p=st.top();  
			if(sq(l[p]-v[p].F)+sq(v[p].S)>sq(l[p]-v[i].F)+sq(v[i].S)){
				l[i]=l[p],r[i]=k;
				l[p]=r[p]=-1;
				st.pop();
			}
			else{
				double ini=l[p],fim=k,ans=-1;
				while(fim-ini>1e-6){
					double mei=(ini+fim)/2.00;
					if(sq(mei-v[p].F)+sq(v[p].S)>sq(mei-v[i].F)+sq(v[i].S)) ans=mei,fim=mei;
					else ini=mei;
				}
				if(ans==-1) l[i]=r[i]=-1;
				else{
					l[i]=ans;
					r[i]=k;
					r[p]=ans;
				}
				break;
			}
		}
		if(r[i]!=-1) st.push(i);
	}
	double ans=0;
	fall(i,0,n-1){
		if(r[i]==-1) continue;
		ans=max(ans,sqrt(sq(l[i]-v[i].F)+sq(v[i].S)));
		ans=max(ans,sqrt(sq(r[i]-v[i].F)+sq(v[i].S)));
	}
	cout.precision(6);
	cout.setf(ios::fixed);
	cout<<ans<<"\n";
}

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