oj.uz

Submission #1118188

# Submission time Handle Problem Language Result Execution time Memory
1118188 2024-11-25T05:15:48 Z bruh Measures (CEOI22_measures) C++14
24 / 100
 320 ms 3656 KB 
#include<bits/stdc++.h>
#define int long long
 
using namespace std;
const int maxn = 2e5 + 100;
int n, m, d;
int a[maxn], pos[maxn];
 
bool check(int dist, int m)
{
    int mid = m / 2 + 1;
    pos[m + 1] = 1e18;
    pos[0] = -1e18;
    for (int i = m; i >= mid; i--)
    {
        pos[i] = min(a[i] + dist, pos[i + 1] - d);
        if (abs(pos[i] - a[i]) > dist) return 0;
    }
    for (int i = 1; i < mid; i++)
    {
        pos[i] = max(a[i] - dist, pos[i - 1] + d);
        if (abs(pos[i] - a[i]) > dist) return 0;
    }
    for (int i = 1; i < m; i++)
        if (pos[i + 1] - pos[i] < d)
            return 0;
    return 1;
}
 
void sub12()
{
    for (int i = 1; i <= m; i++)
    {
        sort(a + 1, a + n + i + 1);
        int l = 0, r = (int)1e15, ans = -1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (check(mid, n + i))
                ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        if (ans % 2) cout << ans / 2 << ".5 ";
        else cout << ans / 2 << " ";
    }
}
 
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("APPLICATION.out", "w", stdout);
    cin >> n >> m >> d;
    d *= 2;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i] *= 2;
    for (int i = 1; i <= m; i++)
        cin >> a[i + n], a[i + n] *= 2;
    if (m <= 10)
        sub12();
//    else sub3();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2384 KB Output is correct
2 Correct 3 ms 2384 KB Output is correct
3 Correct 3 ms 2384 KB Output is correct
4 Correct 3 ms 2384 KB Output is correct
5 Correct 3 ms 2552 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 3 ms 2384 KB Output is correct
8 Correct 3 ms 2384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2384 KB Output is correct
2 Correct 3 ms 2384 KB Output is correct
3 Correct 3 ms 2384 KB Output is correct
4 Correct 3 ms 2384 KB Output is correct
5 Correct 3 ms 2552 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 3 ms 2384 KB Output is correct
8 Correct 3 ms 2384 KB Output is correct
9 Correct 248 ms 3584 KB Output is correct
10 Correct 299 ms 3408 KB Output is correct
11 Correct 197 ms 3408 KB Output is correct
12 Correct 320 ms 3408 KB Output is correct
13 Correct 196 ms 3408 KB Output is correct
14 Correct 238 ms 3408 KB Output is correct
15 Correct 244 ms 3656 KB Output is correct
16 Correct 197 ms 3388 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3408 KB Output isn't correct
2 Halted 0 ms 0 KB -