oj.uz

Submission #1036603

# Submission time Handle Problem Language Result Execution time Memory
1036603 2024-07-27T14:44:06 Z Nonoze Mobile (BOI12_mobile) C++17
100 / 100
 217 ms 35600 KB 
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
using namespace std;

inline namespace IO {
    const int BUFFER_SIZE = 1 << 15;
 
    char input_buffer[BUFFER_SIZE];
    int input_pos = 0, input_len = 0;
 
    char output_buffer[BUFFER_SIZE];
    int output_pos = 0;
 
    char number_buffer[100];
    uint8_t lookup[100];
 
    void _update_input_buffer() {
        input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
        input_pos = 0;
 
        if (input_len == 0)
            input_buffer[0] = EOF;
    }
 
    inline char next_char(bool advance = true) {
        if (input_pos >= input_len)
            _update_input_buffer();
 
        return input_buffer[advance ? input_pos++ : input_pos];
    }
 
    template<typename T> 
    inline void read_int(T &number) {
        bool negative = false;
        number = 0;
 
        while (!isdigit(next_char(false)))
            if (next_char() == '-')
                negative = true;
 
        do {
            number = 10 * number + (next_char() - '0');
        } while (isdigit(next_char(false)));
 
        if (negative)
            number = -number;
    }
 
    template<typename T, typename... Args> 
    inline void read_int(T &number, Args &... args) {
        read_int(number);
        read_int(args...);
    }
 
    void _flush_output() {
        fwrite(output_buffer, sizeof(char), output_pos, stdout);
        output_pos = 0;
    }
 
    inline void write_char(char c) {
        if (output_pos == BUFFER_SIZE)
            _flush_output();
 
        output_buffer[output_pos++] = c;
    }
 
    template<typename T>
    inline void write_int(T number, char after = '\0') {
        if (number < 0) {
            write_char('-');
            number = -number;
        }
 
        int length = 0;
 
        while (number >= 10) {
            uint8_t lookup_value = lookup[number % 100];
            number /= 100;
            number_buffer[length++] = (lookup_value & 15) + '0';
            number_buffer[length++] = (lookup_value >> 4) + '0';
        }
 
        if (number != 0 || length == 0)
            write_char(number + '0');
 
        for (int i = length - 1; i >= 0; i--)
            write_char(number_buffer[i]);
 
        if (after)
            write_char(after);
    }
 
    void init() {
        // Make sure _flush_output() is called at the end of the program.
        bool exit_success = atexit(_flush_output) == 0;
        assert(exit_success);
 
        for (int i = 0; i < 100; i++)
            lookup[i] = (i / 10 << 4) + i % 10;
    }
}
 
int n, L;
vector<pair<double, double>> a;
 
void solve() {
	read_int(n, L);
	a.clear();
	for (int i=0; i<n; i++) {
		int x, y; read_int(x, y);
		if (!a.empty() && x==a.back().first) {
			if (abs(y)<abs(a.back().second)) a.back().second=y;
		}
		else a.push_back({x, y});
	}
	n=sz(a);
	double l=0, r=1e9;
	while (r-l>0.0009) {
		double mid=(l+r)/2;
		double borne=0;
		double popo=pow(mid, 2);
		for (int i=0; i<n; i++) {
			if (abs(a[i].second)>mid) continue;
			double x=a[i].first, y=a[i].second;
			double dist=sqrt(popo-pow(y, 2));
			if (x-dist<=borne && x+dist>borne) borne=x+dist;
		}
		if (borne>=L) r=mid;
		else l=mid;
	}
	cout << fixed << setprecision(3) << l << '\n';
	return;
}
 
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3288 KB Output is correct
2 Correct 11 ms 2540 KB Output is correct
3 Correct 8 ms 2012 KB Output is correct
4 Correct 13 ms 3628 KB Output is correct
5 Correct 2 ms 856 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1372 KB Output is correct
2 Correct 7 ms 2324 KB Output is correct
3 Correct 10 ms 3700 KB Output is correct
4 Correct 11 ms 3832 KB Output is correct
5 Correct 12 ms 3888 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3288 KB Output is correct
2 Correct 10 ms 2524 KB Output is correct
3 Correct 12 ms 3544 KB Output is correct
4 Correct 14 ms 4056 KB Output is correct
5 Correct 5 ms 2012 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2780 KB Output is correct
2 Correct 10 ms 2836 KB Output is correct
3 Correct 5 ms 1760 KB Output is correct
4 Correct 16 ms 4056 KB Output is correct
5 Correct 13 ms 3800 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3800 KB Output is correct
2 Correct 10 ms 2780 KB Output is correct
3 Correct 5 ms 1760 KB Output is correct
4 Correct 13 ms 4088 KB Output is correct
5 Correct 13 ms 3900 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 12728 KB Output is correct
2 Correct 22 ms 8424 KB Output is correct
3 Correct 21 ms 7896 KB Output is correct
4 Correct 63 ms 17788 KB Output is correct
5 Correct 54 ms 14540 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8948 KB Output is correct
2 Correct 119 ms 14784 KB Output is correct
3 Correct 27 ms 7804 KB Output is correct
4 Correct 62 ms 17588 KB Output is correct
5 Correct 66 ms 15004 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 21692 KB Output is correct
2 Correct 26 ms 9832 KB Output is correct
3 Correct 24 ms 9360 KB Output is correct
4 Correct 79 ms 27572 KB Output is correct
5 Correct 60 ms 15808 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 10448 KB Output is correct
2 Correct 136 ms 23996 KB Output is correct
3 Correct 29 ms 9420 KB Output is correct
4 Correct 83 ms 27392 KB Output is correct
5 Correct 75 ms 25584 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21700 KB Output is correct
2 Correct 30 ms 11344 KB Output is correct
3 Correct 29 ms 11020 KB Output is correct
4 Correct 93 ms 27424 KB Output is correct
5 Correct 56 ms 17860 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12140 KB Output is correct
2 Correct 158 ms 23992 KB Output is correct
3 Correct 37 ms 10764 KB Output is correct
4 Correct 90 ms 27064 KB Output is correct
5 Correct 83 ms 25900 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 21696 KB Output is correct
2 Correct 33 ms 12972 KB Output is correct
3 Correct 31 ms 12256 KB Output is correct
4 Correct 99 ms 28664 KB Output is correct
5 Correct 79 ms 19640 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13652 KB Output is correct
2 Correct 168 ms 24248 KB Output is correct
3 Correct 39 ms 11892 KB Output is correct
4 Correct 104 ms 28424 KB Output is correct
5 Correct 90 ms 26292 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 24780 KB Output is correct
2 Correct 43 ms 16024 KB Output is correct
3 Correct 38 ms 15192 KB Output is correct
4 Correct 142 ms 35228 KB Output is correct
5 Correct 82 ms 20916 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17196 KB Output is correct
2 Correct 217 ms 29092 KB Output is correct
3 Correct 55 ms 15192 KB Output is correct
4 Correct 133 ms 35600 KB Output is correct
5 Correct 124 ms 28316 KB Output is correct