Submission #1036607

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1036607	2024-07-27T14:46:34 Z	Nonoze	Mobile (BOI12_mobile)	C++17	100 / 100	197 ms	19140 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 << 16;
 
    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	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 #2
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 #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 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	348 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	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	344 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	2712 KB	Output is correct
2	Correct	11 ms	1496 KB	Output is correct
3	Correct	8 ms	1500 KB	Output is correct
4	Correct	10 ms	2520 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	600 KB	Output is correct
2	Correct	6 ms	1500 KB	Output is correct
3	Correct	10 ms	2516 KB	Output is correct
4	Correct	10 ms	2520 KB	Output is correct
5	Correct	11 ms	2520 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2520 KB	Output is correct
2	Correct	9 ms	1500 KB	Output is correct
3	Correct	11 ms	2520 KB	Output is correct
4	Correct	12 ms	2612 KB	Output is correct
5	Correct	4 ms	992 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1496 KB	Output is correct
2	Correct	8 ms	1500 KB	Output is correct
3	Correct	4 ms	856 KB	Output is correct
4	Correct	12 ms	2520 KB	Output is correct
5	Correct	11 ms	2516 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	2520 KB	Output is correct
2	Correct	9 ms	1496 KB	Output is correct
3	Correct	5 ms	860 KB	Output is correct
4	Correct	12 ms	2520 KB	Output is correct
5	Correct	11 ms	2520 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	9680 KB	Output is correct
2	Correct	13 ms	860 KB	Output is correct
3	Correct	13 ms	860 KB	Output is correct
4	Correct	53 ms	10704 KB	Output is correct
5	Correct	45 ms	9420 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	860 KB	Output is correct
2	Correct	124 ms	9680 KB	Output is correct
3	Correct	21 ms	2516 KB	Output is correct
4	Correct	51 ms	9492 KB	Output is correct
5	Correct	56 ms	8912 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	17356 KB	Output is correct
2	Correct	15 ms	600 KB	Output is correct
3	Correct	21 ms	724 KB	Output is correct
4	Correct	70 ms	18112 KB	Output is correct
5	Correct	47 ms	10632 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	604 KB	Output is correct
2	Correct	147 ms	17044 KB	Output is correct
3	Correct	20 ms	2516 KB	Output is correct
4	Correct	66 ms	17100 KB	Output is correct
5	Correct	65 ms	17096 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	17096 KB	Output is correct
2	Correct	17 ms	604 KB	Output is correct
3	Correct	18 ms	604 KB	Output is correct
4	Correct	77 ms	18620 KB	Output is correct
5	Correct	46 ms	9596 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	600 KB	Output is correct
2	Correct	158 ms	17096 KB	Output is correct
3	Correct	28 ms	2520 KB	Output is correct
4	Correct	77 ms	19140 KB	Output is correct
5	Correct	73 ms	18632 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	115 ms	18728 KB	Output is correct
2	Correct	20 ms	600 KB	Output is correct
3	Correct	18 ms	628 KB	Output is correct
4	Correct	87 ms	17100 KB	Output is correct
5	Correct	69 ms	9676 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	744 KB	Output is correct
2	Correct	178 ms	17096 KB	Output is correct
3	Correct	30 ms	2520 KB	Output is correct
4	Correct	85 ms	17100 KB	Output is correct
5	Correct	89 ms	17096 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	18120 KB	Output is correct
2	Correct	24 ms	604 KB	Output is correct
3	Correct	23 ms	600 KB	Output is correct
4	Correct	105 ms	18892 KB	Output is correct
5	Correct	70 ms	10188 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	600 KB	Output is correct
2	Correct	197 ms	17356 KB	Output is correct
3	Correct	40 ms	5332 KB	Output is correct
4	Correct	109 ms	18380 KB	Output is correct
5	Correct	98 ms	17340 KB	Output is correct

Submission #1036607

Compilation message