Submission #1270535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270535		Mkswll	Mobile (BOI12_mobile)	C++20	50 / 100	814 ms	9256 KiB

mobile

// I will become better someday.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
// typedef long double ld;
typedef double ld;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pdd;
#define debug(x) cout << '[' << #x << ": " << x << "] "
#define cio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define cases int _; cin >> _; while(_--)
#define pb push_back
#define eb emplace_back
#define space << " " <<
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Unique(v) v.erase(unique(all(v)), v.end())
#define mset(x) memset(x, 0, sizeof(x))
#define sflush fflush(stdout)
#define cflush cout.flush()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define lyes cout << "Yes\n"
#define lno cout << "No\n"
#define nl cout << "\n";
#define vt vector
#define ar array
#define uid uniform_int_distribution 

template <typename T> 
istream& operator >> (istream& in, vector<T>& a){
	for(auto &x : a) in >> x; 
	return in;
}

template <typename T> 
ostream& operator << (ostream& out, vector<T>& a){
	for(auto &x : a) out << x << ' '; 
	return out;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

ll read(){
    int w = 1, c;
    ll ret;
    while((c = getchar()) > '9' || c < '0'){
        w = (c == '-' ? -1 : 1);
    }
    ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9'){
        ret = ret * 10 + c - '0';
    }
    return ret * w;
}

ll rd(){
	ll in;
	cin >> in;
	return in;
}
 
void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9){
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

const int MAXN = 3e5 + 5, MAXM = 2e5 + 5, INF = 1e9 + 5, MOD = 1e9 + 7;
const ll LMOD = (ll) 1e18 + 9;
const ll LINF = 1e18 + 5;
const ld ep = 1e-6, Pi = acos(-1.0);

int n, m, k, x; 
pdd a[MAXN];
string s;



void clear(){
    
}

int main(){
    cio;
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
    	cin >> a[i].F >> a[i].S;
    	if (a[i].S < 0) a[i].S = -a[i].S;
    }
    
    auto check = [&](ld d) -> bool {
    	// map<ld, int> dif;
    	vector<pair<ld, int>> dif;
    	dif.eb(0, 0);
    	dif.eb(m, 0);
    	// dif[0];
    	// dif[m];
    	for (int i = 1; i <= n; ++i) {
    		if (a[i].S >= d) continue;
    		ld dx = sqrt(d * d - a[i].S * a[i].S);
    		ld l = a[i].F - dx, r = a[i].F + dx;
    		assert(l <= r);
    		dif.eb(l, 1);
    		dif.eb(r, -1);
    		// dif[l]++;
    		// dif[r]--;
    	}
    	sort(all(dif), [](auto& x, auto& y) {
    		return (fabs(x.F - y.F) < ep ? x.S > y.S : x < y);
    	});
    	int cur = 0;
    	for (auto [u, v] : dif) {
    		cur += v;
    		if (u + ep >= 0 && u - ep <= m && !cur) {
    			return 1;
    		}
    	}
    	return 0;
    };
    
    ld l = 0, r = 1e10, res = l;
    while (l + ep < r) {
    	ld mid = (l + r) / 2;
    	if (check(mid)) {
    		res = mid;
    		l = mid;
    	}
    	else r = mid;
    }
    
    cout << fixed << setprecision(10) << res << "\n";
    
    return 0;
}   

• 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: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5