Submission #1036606

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1036606	2024-07-27T14:45:46 Z	Nonoze	Mobile (BOI12_mobile)	C++17	100 / 100	223 ms	33864 KB

mobile

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define sz(x) (int)(x.size())
using namespace std;

inline namespace IO {
    const int BUFFER_SIZE = 1 << 17;
 
    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	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	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	480 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	348 KB	Output is correct
4	Correct	1 ms	796 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 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	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
5	Correct	0 ms	348 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	3544 KB	Output is correct
2	Correct	9 ms	2620 KB	Output is correct
3	Correct	8 ms	2268 KB	Output is correct
4	Correct	11 ms	3800 KB	Output is correct
5	Correct	1 ms	984 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	2524 KB	Output is correct
3	Correct	10 ms	3796 KB	Output is correct
4	Correct	11 ms	3840 KB	Output is correct
5	Correct	11 ms	4056 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	2608 KB	Output is correct
3	Correct	11 ms	3544 KB	Output is correct
4	Correct	12 ms	4056 KB	Output is correct
5	Correct	4 ms	2016 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	3036 KB	Output is correct
2	Correct	8 ms	3036 KB	Output is correct
3	Correct	4 ms	1760 KB	Output is correct
4	Correct	12 ms	4056 KB	Output is correct
5	Correct	11 ms	3800 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	3796 KB	Output is correct
2	Correct	9 ms	3036 KB	Output is correct
3	Correct	4 ms	1800 KB	Output is correct
4	Correct	12 ms	4056 KB	Output is correct
5	Correct	12 ms	3800 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	12732 KB	Output is correct
2	Correct	19 ms	8528 KB	Output is correct
3	Correct	16 ms	7980 KB	Output is correct
4	Correct	58 ms	17848 KB	Output is correct
5	Correct	50 ms	14648 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	8916 KB	Output is correct
2	Correct	130 ms	15040 KB	Output is correct
3	Correct	23 ms	7892 KB	Output is correct
4	Correct	59 ms	17596 KB	Output is correct
5	Correct	59 ms	14980 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	21836 KB	Output is correct
2	Correct	19 ms	9812 KB	Output is correct
3	Correct	18 ms	9044 KB	Output is correct
4	Correct	72 ms	27296 KB	Output is correct
5	Correct	53 ms	16080 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	10376 KB	Output is correct
2	Correct	151 ms	23472 KB	Output is correct
3	Correct	22 ms	9164 KB	Output is correct
4	Correct	74 ms	26804 KB	Output is correct
5	Correct	72 ms	25192 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	104 ms	21424 KB	Output is correct
2	Correct	22 ms	10772 KB	Output is correct
3	Correct	20 ms	9972 KB	Output is correct
4	Correct	83 ms	26544 KB	Output is correct
5	Correct	53 ms	17152 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	11264 KB	Output is correct
2	Correct	164 ms	23816 KB	Output is correct
3	Correct	33 ms	10184 KB	Output is correct
4	Correct	80 ms	26032 KB	Output is correct
5	Correct	80 ms	25208 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	21696 KB	Output is correct
2	Correct	24 ms	12040 KB	Output is correct
3	Correct	24 ms	11448 KB	Output is correct
4	Correct	86 ms	27548 KB	Output is correct
5	Correct	74 ms	18616 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	12628 KB	Output is correct
2	Correct	174 ms	23580 KB	Output is correct
3	Correct	34 ms	11460 KB	Output is correct
4	Correct	98 ms	27116 KB	Output is correct
5	Correct	86 ms	25520 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	156 ms	24152 KB	Output is correct
2	Correct	31 ms	14748 KB	Output is correct
3	Correct	29 ms	13640 KB	Output is correct
4	Correct	120 ms	33440 KB	Output is correct
5	Correct	87 ms	19456 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	15440 KB	Output is correct
2	Correct	223 ms	28068 KB	Output is correct
3	Correct	43 ms	15048 KB	Output is correct
4	Correct	119 ms	33864 KB	Output is correct
5	Correct	106 ms	27052 KB	Output is correct

Submission #1036606

Compilation message