| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 859434 | Alexandruabcde | Measures (CEOI22_measures) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 2e5 + 5;
typedef long long LL;
typedef long double LD;
constexpr LL INF = 1LL * 1e18;
int N, M, D;
int A[NMAX];
int B[NMAX];
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> D;
for (int i = 1; i <= N; ++ i )
cin >> A[i];
for (int i = 1; i <= M; ++ i )
cin >> B[i];
}
bool Check (LD t, int m) {
LD first_dist = -INF;
int i = 1, j = 1;
while (i <= N || j <= m) {
LD next_dist = 0;
if (i <= N && (A[i] <= B[j] || j > m)) {
next_dist = max(first_dist + D, A[i] - t);
if (next_dist < A[i] - t || next_dist > A[i] + t) return false;
++ i;
}
else {
next_dist = max(first_dist + D, B[j] - t);
if (next_dist < B[j] - t || next_dist > B[j] + t) return false;
++ j;
}
first_dist = next_dist;
}
return true;
}
void Solve_FirstCase () {
sort(A+1, A+N+1);
for (int i = 1; i <= M; ++ i ) {
sort(B+1, B+i+1);
LL st = 0, dr = INF;
LD ans = 0;
while (st <= dr) {
LL mij = (st + dr) / 2;
if (Check(mij*.5, i)) {
dr = mij - 1;
ans = mij * .5;
}
else st = mij + 1;
}
cout << ans << " ";
}
}
void Solve_SecondCase () {
LL worst_case = -INF;
LD answer = 0;
for (int j = 1; j <= M; ++ j ) {
LL new_pos_ans = 1LL * j * D - B[j] + worst_case;
answer = max(answer, new_pos_ans * .5);
cout << answer << '\n';
worst_case = max(worst_case, B[j] - 1LL * j * D);
}
}
int main()
{
Read();
if (M <= 10)
Solve_FirstCase();
else Solve_SecondCase();
return 0;
}