oj.uz

Submission #739910

# Submission time Handle Problem Language Result Execution time Memory
739910 2023-05-11T15:10:14 Z danikoynov Measures (CEOI22_measures) C++14
24 / 100
 1500 ms 3900 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 4e5 + 10;

int n, m;
ll d, a[maxn], b[maxn];

bool check(double x)
{
    double last = -1e18;
    for (int i = 1; i <= n; i ++)
    {
        if (last + d > a[i] + x)
            return false;
        last = max(last + d, a[i] - x);
        //cout << last << " " << a[i] << endl;
    }
    return true;
}

void solve_query()
{
    sort(a + 1, a + n + 1);
    ll lf = 0, rf = 1e18;
    //cout << check(684538602442.5) << endl;
    //exit(0);
    while(lf <= rf)
    {
        ll mf = (lf + rf) / 2;
        //cout << lf << " " << rf << endl;
        if (check(mf))
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    double ans = lf;
    if (ans > 0 && check(ans - 0.5))
    {
        ans = ans - 0.5;
        printf("%0.1f ", ans);
    }
    else
    {
        cout << (ll)(round(ans)) << " ";
    }
}
void solve()
{
    cin >> n >> m >> d;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 1; i <= m; i ++)
        cin >> b[i];

    for (int i = 1; i <= m; i ++)
    {
        n ++;
        a[n] = b[i];
        solve_query();
    }

}

int main()
{
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 3 ms 328 KB Output is correct
3 Correct 3 ms 212 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 212 KB Output is correct
9 Correct 356 ms 1868 KB Output is correct
10 Correct 401 ms 3736 KB Output is correct
11 Correct 287 ms 3820 KB Output is correct
12 Correct 426 ms 3864 KB Output is correct
13 Correct 279 ms 3272 KB Output is correct
14 Correct 343 ms 3900 KB Output is correct
15 Correct 328 ms 3128 KB Output is correct
16 Correct 295 ms 3788 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 1992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 1992 KB Time limit exceeded
2 Halted 0 ms 0 KB -